uva 12424 Answering Queries on a Tree

本文从WordPress迁移而来, 查看全部WordPress迁移文章

【UVA提交失败，无法评判】

LCA + 树状数组（线段树）

题意：给出一棵无根树，每个点有颜色，颜色种类只有10种，从1到10标号。有两种操作，一种是改变某个点的颜色，一种是询问点u到v的路径中，出现的次数最多的颜色（输出次数，不是输出对应的颜色标号）。

这题的巧妙之处是，怎么引入线段树？

这题一个重要的突破口是，颜色10种，这是个可以暴力枚举的特征。可以先考虑询问操作。入股我们定义一个dp值，dp[u][col]，表示点u到根的路径上，col这种颜色出现了几次。那么就可以跟LCA联系起来。对于询问（u，v）可以先找到LCA，然后枚举每一种颜色，看看u到v的路径上，这种颜色出现了几次

cnt[col] = dp[u][col] + dp[v][col] - 2*dp[lca][col] + (color[lca] == col)

这个式子是很容易理解的，注意最后，如果lca这个点的颜色就是col，加1，否则加0
上面是计算出了1种颜色，那么对应10颜色，就枚举10次，找到最大的cnt[col]，就是答案
所以我们要做的就是能维护这个dp数组。要维护就用到了线段树。

我们在求LCA的时候，要用ST算法，是因为，这样才能得到一个序列，一个区间，这才用上线段树，但是和一般的LCA转RMQ不同，要另外构建一个序列
sample：对于一个树，定1为根

1
2
3
4
1 2
1 3
2 4
2 5

LCA转RMQ得到的序列为

1
2
1 2 4 2 5 2 1 3 1  ， 这个序列用于ST算法求LCA
1 2 4 4 5 5 2 3 3 1 ， 这个序列是dfs的时候

另外构建的，这个序列的含义很显然，每个节点首次和末次出现的时候都记录了一次，一共记录了2n个节点。我们设置2个数组记录一些信息，L[u]表示点u首次出现的位置,R[u]表示末次出现的位置。

我们用10个树状数组（或线段树，这里其实树状数组更方便），维护信息，10个树状数组是对应10种颜色。

如果一个节点u变色为col，那么就将L[u]这个位置边为1，R[u]这个位置边为-1，（如果是从一个颜色变为另一个颜色，旧的颜色对应的位置L[u] = R[u] = 0）。

我们可以看一个sample，询问4,5的LCA，那就是2，找到L[4],L[5],L[2]从这些位置开始计算一次前缀和，用4,5的前缀和减去2倍2的前缀和，就是4到5的路径上这个颜色出现了多少次

这题是近期做的比较好的一题，要说清楚有些困难，可以看看代码领悟一下。不过代码不能提交不知道对错，自己测过一些数据是对的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define N 100010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int Pow[25];
int n,color[N],dep[N],first[N],L[N],R[N];
int Node[2*N],Dep[2*N]; //两个对应的序列，一个记录遍历时节点编号和对应节点的深度
int dp[2*N][25];
int head[N],tot; //建树，树边数
int tree[2*N][15];
struct edge{
	int u,v,next;
}e[2*N];

void Test(){
	for(int i = 1; i <= 2*n-1; i++)
		printf("%d[%d] ",Node[i],Dep[i]);
	cout << endl;
}

inline int lowbit(int x){
	return x & (-x);
}

inline void add(int u ,int v){
	e[tot].u = u; e[tot].v = v;
	e[tot].next = head[u]; head[u] = tot++;
}

void dfs(int u,int fa,int depth,int &index,int &cnt){
	first[u] = ++index; Node[index] = u; Dep[index] = depth;
	L[u] = ++cnt;
	dep[u] = depth;
	for(int k = head[u]; k != -1; k = e[k].next){
		int v = e[k].v;
		if(v == fa) continue;
		dfs(v,u,depth+1,index,cnt);
		Node[++index] = u; Dep[index] = depth;
	}
	R[u] = ++cnt;
}

void ST(int len){
	int K = (int)(log((double)len) / log(2.0));
	for(int i = 1; i <= len; i++)
		dp[i][0] = i;
	for(int j = 1; j <= K; j++){
		for(int i = 1; i+Pow[j]-1 <= len; i++){
			int x = dp[i][j-1];
			int y = dp[i+Pow[j-1]][j-1];
			if(Dep[x] < Dep[y]) 
				dp[i][j] = x;
			else 
				dp[i][j] = y;
		}
	}
}

int RMQ(int l,int r){
	if(l > r) swap(l,r);
	int K = (int)(log((double)(r-l+1)) / log(2.0));
	int x = dp[l][K];
	int y = dp[r-Pow[K]+1][K];
	if(Dep[x] < Dep[y]) return x;
	else  return y;
}

int LCA(int u,int v){
	int res = RMQ(first[u],first[v]);
	return Node[res];
}

int sum(int p,int col){ //树状数组求前缀和
	int res = 0;
	while(p){
		res += tree[p][col];
		p -= lowbit(p);
	}
	return res;
}

void updata(int p,int col,int k){ //树状数组单点更新
	while(p <= 2*n){
		tree[p][col] += k;
		p += lowbit(p);
	}
}

void Init(){
	int index = 0,cnt = 0;
	dfs(1,-1,0,index,cnt);
	ST(2*n-1);
	cl(tree,0);
	for(int i = 1; i <= n; i++){ //初始化树状数组
		updata(L[i],color[i],1);
		updata(R[i],color[i],-1);
	}
	//Test();
}

int main(){
	freopen("__case.txt","r",stdin);
	freopen("grated.txt","w",stdout);
	for(int i = 0;  i < 25; i++) 
		Pow[i] = (1<<i);
	int m,cas;
	scanf("%d",&cas);
	while(cas--){
		scanf("%d%d",&n,&m);
		for(int i = 1; i <= n; i++)
			scanf("%d",&color[i]);
		cl(head,-1); tot = 0;
		for(int i = 1; i < n; i++){
			int u,v;
			scanf("%d%d",&u,&v);
			add(u,v); add(v,u);
		}
		Init();
		while(m--){
			int op;
			scanf("%d",&op);
			if(op == 1){
				int u,v,ans;
				scanf("%d%d",&u,&v);
				int lca = LCA(u,v);
				//printf("lca = %d\n",lca);
				ans = 0;
				for(int col = 1; col <= 10; col++){
					int sumu = sum(L[u],col); //树状数组计算前缀和
					int sumv = sum(L[v],col);
					int sumlca = sum(L[lca],col);
					int delta = (color[lca] == col ? 1 : 0);
					ans = max(ans,sumu+sumv-2*sumlca+delta);
				}
				printf("%d\n",ans);
			}
			else{
				int u,col;
				scanf("%d%d",&u,&col);
				if(col == color[u]) continue;
				updata(L[u],color[u],-1);
				updata(R[u],color[u],1);
				updata(L[u],col,1);
				updata(R[u],col,-1);
				color[u] = col;
			}
		}
	}
	return 0;
}