2017 ICPC网络赛（西安）--- Xor

题目连接

 

problem

there is a tree with n nodes. for each node, there is an integer value ai, (1≤ai​≤1,000,000,000 for 1≤i≤n). there is q queries which are described as follow:

assume the value on the path from node a to node b is t0​,t1​,⋯tm​. you are supposed to calculate t0 xor tk xor t2k xor ... xor tpk (pk≤m).

input format

there are multi datasets. (∑n≤50,000,∑q≤500,000).

for each dataset: in the first n−1 lines, there are two integers u,v, indicates there is an edge connect node uand node v.

in the next nn lines, there is an integer ai​ (1≤ai​≤1,000,000,000).

in the next q lines, there is three integers a,b and k. (1≤a,b,k≤n).

output format

for each query, output an integer in one line, without any additional space.

样例输入

5 6
1 5
4 1
2 1
3 2
19
26
0
8
17
5 5 1
1 3 2
3 2 1
5 4 2
3 4 4
1 4 5

样例输出

17
19
26
25
0
19

题意： 有一棵n个节点的树，每个节点上有个权值vi，现在q次询问：节点a到节点b的路径上，从a开始每k个节点跳一次所经过的所有节点的异或值为（a0,ak,a2k,a3k...）？

思路： 建树，倍增算法记录每个节点的深度和2^i的祖先，处理并记录每个节点i到根节点间隔为k（1,2,3……100）的异或值dp[i][k]。当k<=100时，使用记录的异或值dp计算a到b间隔为k的异或值；当k>100时，直接从a走到b，每次跳动使用倍增的信息（快速跳动）。

注：这道题是2017年打西安网络赛时没过的题，当时其实代码写的很接近了，测数据都没问题，一直检查不出来，我也一直惦记着这道题。本科毕业后读研，又看过一次还是没找出原因，今天五一放假，没啥事儿，我又看了一遍当时写的代码，突然发现没初始化fa数组，心想难道是计蒜客网站编译器不是默认未初始化的值为0？加上fa的初始化后提交了一把，过了！！！
my god！ 心心念念的这道题竟然是这个原因没过，气呀。不过，今天总算是找到原因了，哈哈~  又一次想起来西安正式赛的时候，一道铜牌题没过“lol bp”导致没拿到银牌，可惜的是当时的银牌题都过了，唉~ 与银失之交臂。现在是研究生了，很少刷题了，以后要少看剧，多看看相关的图形学的专业书，充实自己，找个好工作。

代码如下：

  1 //https://nanti.jisuanke.com/t/a1273 《xor》
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstdio>
  5 #include <cstring>
  6 using namespace std;
  7 const int n = 5e4 + 5;
  8 int fa[n][20], deep[n], head[n];
  9 int v[n], cnt;
 10 bool vis[n];
 11 int dp[n][105];
 12 struct data
 13 {
 14     int to, next;
 15 }e[2 * n];
 16 
 17 void insert(int u, int v)
 18 {
 19     e[++cnt].to = v;
 20     e[cnt].next = head[u];
 21     head[u] = cnt;
 22     e[++cnt].to = u;
 23     e[cnt].next = head[v];
 24     head[v] = cnt;
 25 }
 26 int cal(int x, int t)
 27 {
 28     for (int i = 0; i <= 19; i++)
 29         if (t&(1 << i)) x = fa[x][i];
 30     return x;
 31 }
 32 void dfs(int x)
 33 {
 34     vis[x] = 1;
 35     for (int i = 1; i <= 19; i++)
 36     {
 37         if (deep[x]<(1 << i))break;
 38         fa[x][i] = fa[fa[x][i - 1]][i - 1];///倍增处理祖先信息
 39     }
 40     for (int k = 1; k <= 100; k++)
 41     {
 42         dp[x][k] = v[x];
 43         if (deep[x]<k) continue;
 44         int p = cal(x, k);
 45         dp[x][k] ^= dp[p][k];
 46     }
 47     for (int i = head[x]; i; i = e[i].next)
 48     {
 49         if (vis[e[i].to]) continue;
 50         deep[e[i].to] = deep[x] + 1;
 51         fa[e[i].to][0] = x;
 52         dfs(e[i].to);
 53     }
 54 }
 55 int lca(int x, int y)///求lca
 56 {
 57     if (deep[x]<deep[y]) swap(x, y);
 58     x = cal(x, deep[x] - deep[y]);
 59     for (int i = 19; i >= 0; i--)
 60         if (fa[x][i] != fa[y][i])
 61         {
 62             x = fa[x][i];
 63             y = fa[y][i];
 64         }
 65     if (x == y)return x;
 66     else return fa[x][0];
 67 }
 68 
 69 void init()
 70 {
 71     cnt = 0;
 72     memset(head, 0, sizeof(head));
 73     memset(vis, 0, sizeof(vis));
 74     memset(dp, 0, sizeof(dp));
 75     memset(deep, 0, sizeof(deep));
 76     memset(fa,0,sizeof(fa));
 77 }
 78 
 79 int main()
 80 {
 81     int n, q;
 82     while (scanf("%d%d", &n, &q) != eof)
 83     {
 84         init();
 85         for (int i = 1; i<n; i++)
 86         {
 87             int x, y; scanf("%d%d", &x, &y);
 88             insert(x, y);
 89         }
 90         for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
 91         dfs(1);
 92         while (q--)
 93         {
 94             int x, y, k; scanf("%d%d%d", &x, &y, &k);
 95             int pa = lca(x, y);
 96             if (k <= 100)
 97             {
 98                 int ans = dp[x][k];
 99                 int h = (deep[x] - deep[pa]) % k;
100                 int t = k - h;
101                 if (deep[pa] >= t)
102                 {
103                     int l = cal(pa, t);
104                     ans ^= dp[l][k];
105                 }
106                 int r = k - h;
107                 t = deep[y] - deep[pa] - r;
108                 if (t<0) goto endw2;
109                 t %= k;
110                 y = cal(y, t);///
111                 ans ^= dp[y][k];
112                 t = k - r;
113                 if (deep[pa] >= t)
114                 {
115                     int l = cal(pa, t);
116                     ans ^= dp[l][k];
117                 }
118             endw2:;
119                 printf("%d\n", ans);
120             }
121             else
122             {
123                 int ans = 0;
124                 while (1)
125                 {
126                     ans ^= v[x];
127                     if (deep[x] - k<deep[pa]) break;
128                     x = cal(x, k);
129                 }
130                 int l = k - (deep[x] - deep[pa]);
131                 int t = deep[y] - deep[pa] - l;
132                 if (t<0) goto endw;
133                 t %= k;
134                 y = cal(y, t);
135                 while (1)
136                 {
137                     ans ^= v[y];
138                     if (deep[y] - k <= deep[pa]) break;
139                     y = cal(y, k);
140                 }
141             endw:;
142                 printf("%d\n", ans);
143             }
144         }
145     }
146     return 0;
147 }
148 /**
149 8 11
150 1 2
151 2 3
152 2 4
153 1 5
154 5 6
155 5 7
156 4 8
157 3 5 6 2 7 0 1 10
158 1 8 1
159 answer=14
160 */