【bzoj4999】This Problem Is Too Simple！树链剖分+动态开点线段树-白红宇

【bzoj4999】This Problem Is Too Simple！树链剖分+动态开点线段树

阅读量：4582 次

发布时间：2019-06-09

本文共 2833 字，大约阅读时间需要 9 分钟。

题目描述

给您一颗树，每个节点有个初始值。

现在支持以下两种操作：

1. C i x(0<=x<2^31) 表示将i节点的值改为x。

2. Q i j x(0<=x<2^31) 表示询问i节点到j节点的路径上有多少个值为x的节点。

输入

第一行有两个整数N,Q（1 ≤N≤ 100,000；1 ≤Q≤ 200,000），分别表示节点个数和操作个数。

下面一行N个整数，表示初始时每个节点的初始值。

接下来N-1行，每行两个整数x,y，表示x节点与y节点之间有边直接相连（描述一颗树）。

接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出。

输出

对于每个Q输出单独一行表示所求的答案。

样例输入

5 6

10 20 30 40 50

1 2

1 3

3 4

3 5

Q 2 3 40

C 1 40

Q 2 3 40

Q 4 5 30

C 3 10

Q 4 5 30

样例输出

题解

树链剖分+动态开点线段树

对树轻重链剖分，对每个权值开一棵动态开点线段树，修改时相当于删除再加入，查询时直接查询链上信息即可。

时间复杂度$O(m\log^2n)$，有更优秀的$O((m+n)\log n)$解法，但在本题中好像没什么必要= =

#include #include 
      
       #include 
       
        #define N 100010#define lson l , mid , ls[x]#define rson mid + 1 , r , rs[x]using namespace std;map
        
          mp;int a[N] , head[N] , to[N << 1] , next[N << 1] , cnt , fa[N] , deep[N] , si[N] , bl[N] , pos[N] , num;int root[N << 2] , ls[N << 7] , rs[N << 7] , sum[N << 7] , tot , n , clo;char str[5];void add(int x , int y){	to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;}void dfs1(int x){	int i;	si[x] = 1;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x])			fa[to[i]] = x , deep[to[i]] = deep[x] + 1 , dfs1(to[i]) , si[x] += si[to[i]];}void dfs2(int x , int c){	int i , k = 0;	bl[x] = c , pos[x] = ++num;	for(i = head[x] ; i ; i = next[i])		if(to[i] != fa[x] && si[to[i]] > si[k])			k = to[i];	if(k)	{		dfs2(k , c);		for(i = head[x] ; i ; i = next[i])			if(to[i] != fa[x] && to[i] != k)				dfs2(to[i] , to[i]);	}}void update(int p , int a , int l , int r , int &x){	if(!x) x = ++tot;	sum[x] += a;	if(l == r) return;	int mid = (l + r) >> 1;	if(p <= mid) update(p , a , lson);	else update(p , a , rson);}int query(int b , int e , int l , int r , int x){	if(!x) return 0;	if(b <= l && r <= e) return sum[x];	int mid = (l + r) >> 1 , ans = 0;	if(b <= mid) ans += query(b , e , lson);	if(e > mid) ans += query(b , e , rson);	return ans;}int solve(int x , int y , int c){	int ans = 0;	while(bl[x] != bl[y])	{		if(deep[bl[x]] < deep[bl[y]]) swap(x , y);		ans += query(pos[bl[x]] , pos[x] , 1 , n , root[c]) , x = fa[bl[x]];	}	if(deep[x] > deep[y]) swap(x , y);	ans += query(pos[x] , pos[y] , 1 , n , root[c]);	return ans;}int main(){	int m , i , x , y , z;	scanf("%d%d" , &n , &m);	for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);	for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);	dfs1(1) , dfs2(1 , 1);	for(i = 1 ; i <= n ; i ++ )	{		if(!mp[a[i]]) mp[a[i]] = ++clo;		update(pos[i] , 1 , 1 , n , root[mp[a[i]]]);	}	while(m -- )	{		scanf("%s%d%d" , str , &x , &y);		if(str[0] == 'C')		{			update(pos[x] , -1 , 1 , n , root[mp[a[x]]]);			if(!mp[y]) mp[y] = ++clo;			update(pos[x] , 1 , 1 , n , root[mp[y]]);			a[x] = y;		}		else		{			scanf("%d" , &z);			if(!mp[z]) puts("0");			else printf("%d\n" , solve(x , y , mp[z]));		}	}	return 0;}