bzoj 2589 Count on a tree II
Description
给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v)，你需要回答u xor lastans和v这两个节点间有多少种不同的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。
Input
第一行两个整数N,M。 第二行有N个整数，其中第i个整数表示点i的权值。 后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。 最后M行每行两个整数(u,v)，表示一组询问。SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 数据范围是N<=40000 M<=100000 点权在int范围内
Output
M行，表示每个询问的答案。Sample Input
8 2105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
3 8
Sample Output
44 思路： 这题的原先版本是spoj上的题目，那个题目没有强制要求在线，可以使用树上莫队ac。 本题强制要求在线，所以我们要在树上采用分块方法，然后采用类似莫队的思想。 首先，把树分成n^(1/3) 块。 每个块定一个点作为中心，预处理两两中心之间的答案。然后每次询问找到那两个点的中心，像莫队那样暴力移动。显然每次最多移动n^(2/3)次。 所以复杂度m*n^(2/3)。 这样的时间复杂度理论上可以通过的，但是bzoj的服务器实在太弱了，于是被卡常了。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int const N = 40000 + 3; 4 int const M = 100000 + 3; 5 int const C = 40; 6 struct edge { 7 int to, nt; 8 } e[N << 1]; 9 int tin[N], tout[N], h[N], cnt, sum, dep[N], f[N][16], a[N], b[N], n, m, st[N], top, sz, bl[N], num, cap[42]; 10 int c[42][42][N], kind[42][42], last; 11 bool vis[42][42][N]; 12 template<class T>void read(T &x) { 13 x = 0; 14 char c = 0; 15 while(!isdigit(c)) c = getchar(); 16 while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); 17 } 18 void dfs(int x, int fa) { 19 tin[x] = ++sum; 20 f[x][0] = fa; 21 dep[x] = dep[fa] + 1; 22 for(int i = h[x]; i; i = e[i].nt) { 23 int v = e[i].to; 24 if(v == fa) continue; 25 dfs(v, x); 26 } 27 tout[x] = ++sum; 28 } 29 30 void add(int a, int b) { 31 e[++cnt].to = b; 32 e[cnt].nt = h[a]; 33 h[a] = cnt; 34 } 35 void dfs2(int x, int fa) { 36 int now = top; 37 for(int i = h[x]; i; i = e[i].nt) { 38 int v = e[i].to; 39 if(v == fa) continue; 40 dfs2(v, x); 41 int tmp = top - now; 42 if(tmp >= sz) { 43 num++; 44 while(tmp--) { 45 int t = st[top--]; 46 cap[num] = x; 47 bl[t] = num; 48 } 49 } 50 } 51 st[++top] = x; 52 } 53 int ancestor(int x, int y) { 54 return tin[x] <= tin[y] && tout[y] <= tout[x]; 55 } 56 int lca(int x, int y) { 57 if(ancestor(x, y)) return x; 58 if(ancestor(y, x)) return y; 59 for(int i = 15; i >= 0; i--) 60 if(!ancestor(f[x][i], y)) 61 x = f[x][i]; 62 return f[x][0]; 63 } 64 int update(int i, int j, int x) { 65 if(vis[i][j][x]) { 66 if(--c[i][j][a[x]] == 0) --kind[i][j]; 67 } else { 68 if(++c[i][j][a[x]] == 1) ++kind[i][j]; 69 } 70 vis[i][j][x] ^= 1; 71 } 72 int calc(int i, int j, int x, int y) { 73 if(dep[x] < dep[y]) 74 swap(x, y); 75 while(dep[x] > dep[y]) { 76 update(i, j, x); 77 x = f[x][0]; 78 } 79 while(x ^ y) { 80 update(i, j, x); 81 update(i, j, y); 82 x = f[x][0]; 83 y = f[y][0]; 84 } 85 } 86 int main() { 87 scanf("%d%d", &n, &m); 88 sz = max(1, n / C); 89 for(int i = 1; i <= n; i++) 90 read(a[i]), b[i] = a[i]; 91 sort(b + 1, b + n + 1); 92 int k = unique(b + 1, b + n + 1) - b - 1; 93 for(int i = 1; i <= n; i++) 94 a[i] = lower_bound(b + 1, b + k + 1, a[i]) - b; 95 for(int i = 1; i < n; i++) { 96 int x, y; 97 read(x); 98 read(y); 99 add(x, y); 100 add(y, x); 101 } 102 dfs(1, 1); 103 for(int j = 1; j <= 15; j++) 104 for(int i = 1; i <= n; i++) 105 f[i][j] = f[f[i][j - 1]][j - 1]; 106 dfs2(1, 1); 107 if(top) { 108 ++num; 109 cap[num] = 1; 110 while(top) bl[st[top--]] = num; 111 } 112 for(int i = 1; i <= num; i++) 113 for(int j = i + 1; j <= num; j++) { 114 calc(i, j, cap[i], cap[j]); 115 } 116 while(m--) { 117 int x, y; 118 read(x); 119 read(y); 120 x ^= last; 121 int c = min(bl[x], bl[y]); 122 int d = max(bl[x], bl[y]); 123 calc(c, d, cap[bl[x]], x); 124 calc(c, d, cap[bl[y]], y); 125 update(c, d, lca(x, y)); 126 printf("%d\n", last = kind[c][d]); 127 calc(c, d, cap[bl[x]], x); 128 calc(c, d, cap[bl[y]], y); 129 update(c, d, lca(x, y)); 130 } 131 return 0; 132 }View Code
更多精彩
