PSHTTR: Pishty 和城堡
题目描述
Pishty 是生活在胡斯特市的一个小男孩。胡斯特是胡克兰境内的一个古城，以其中世纪风格
的古堡和非常聪明的熊闻名全国。
胡斯特的镇城之宝是就是这么一座古堡，历史上胡斯特依靠这座古堡抵挡住了疯人国的大军。
对于 Pishty 来说，真正吸引他的是古堡悠长的走廊和高耸的钟楼，以及深藏于其中的秘密……
古堡可以用一棵 N 个节点的树的描述，树中有 N − 1 条无向边，每条边有一个魔法数字 C。
当一个旅游团参观古堡时，他们会选择树上 U 到 V 的路径游览。他们认为，如果一条边的魔
法数字不超过 K，那么这条边是有趣的。而一条路径的吸引力就是路径上所有有趣的边的魔法数
字的异或和。
胡克兰的国王希望大力发展旅游业，因此他下令求出所有旅游团的游览路径的吸引力。而
Pishty 立志成为国王身边的骑士，便自告奋勇承担了这一任务。但旅游团实在太多了，他也算不过
来。所以，请你帮 Pishty 解决这一问题：给定 M 个旅游团的旅游路径，请你求出路径的吸引力。
输入格式
输入的第一行包含一个整数 T，代表测试数据的组数。接下来是 T 组数据。
每组数据的第一行包含一个整数 N，代表树的节点个数。
接下来 N - 1 行，每行描述一条边。每行包含三个整数 U, V, C，代表节点 U 和 V 之间连有
一条魔法数字为 C 的边。
接下来一行包含一个整数 M，代表旅游团的数量。
接下来 M 行，每行包含三个整数 U, V, K，描述一个旅游团。
输出格式
对于每个旅游团，输出一行，包含一个整数，代表其路径的吸引力。
数据范围和子任务
• 1 ≤ T ≤ 5
• 1 ≤ N, M ≤ 105
• 1 ≤ U, V ≤ N
• 1 ≤ C, K ≤ 109
子任务 1（10 分）：
• 1 ≤ N, M ≤ 10
子任务 2（20 分）：
• 1 ≤ N, M ≤ 103
子任务 3（70 分）：
• 无附加限制
样例数据
输入
1
5
1 2 1
2 3 2
2 4 5
3 5 10
6
5 4 5
5 4 10
5 4 1
1 2 1
4 1 10
1 5 8
输出
7
13
0
1
4
3
题目的意思很清楚，求树上两点间，所有权值不超过一定范围的边的xor和。那么，一般求树上距离（不一定是严格意义上的距离），都可以用树剖来做。但是，这题有个小小的弯路：有些边尽管在路径上，却不能算进来，这就略为复杂一些了。怎么办？稍微有些麻烦。但是，如果我们提前知道哪些边会被加进来，那不是就好办了吗？所以，有个离线的想法。将树边的权值从小到大排趟序，这样，我们可以将这些边有序的加入“可用集合”当中，前一条边一定比后一条边先加入。与此同时，我们也要将Q次询问按照限定权值的大小进行从小到大的排序。这样，我们能够用O(n+Q)的时间将所以边加入集合。但是还有一个问题。这些边加入到哪里呢？由于xor的特殊性质 X xor 0=X，所以没有加入的边，其权值可以先赋0，加入的边，其权值赋其真实权。由于我们要充分运用树剖的威力，所以，我们必然要在每一条重路径上面做文章。而我们知道，树剖的核心思想就是将树上的一个个点转为一定顺序的序列，也就是DFS序。那么对于同一条重路径上面的点（映射到序列中是一段连续区间），可以通过线段树将区间进行修改并求出答案。至此，本题就解完了，其时间复杂度为O(T*Q*(log^2)n)。
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<vector>
5 #define M(A) memset(A,0,sizeof A);
6 #define mid ((L+R)>>1)
7 using namespace std;
8 const int maxn=100005,maxe=200005;
9
10 int n,Q,fa[maxn],dep[maxn],size[maxn],gonxt[maxn];
11 int top[maxn],bel[maxn],num[maxn],cnt;
12 int pos[maxn],who[maxn],cloc;
13 int finalans[100005];
14
15 struct weight{
16 int x,i;
17 bool operator < (const weight &other) const {return x<other.x;}
18 }wtofa[maxn];
19
20 struct segment_tree{
21 int Toge,key;
22 }T[maxn*20];
23
24 struct edge{
25 int nxt[maxe],son[maxe],w[maxe],lnk[maxn],tot;
26 bool cmp(edge &x,edge &y){return x.w<y.w;}
27 void clear(){tot=cnt=cloc=0; M(nxt); M(son); M(w); M(lnk); M(gonxt);}
28 void add(int x,int y,int z){nxt[++tot]=lnk[x],son[tot]=y,w[tot]=z,lnk[x]=tot;}
29 }G;
30
31 struct queries{
32 int x,y,z,i;
33 bool operator < (const queries &other) const {return z<other.z;}
34 }que[100005];
35
36 inline int read(){
37 int x=0; char ch=getchar();
38 while (ch<'0'||ch>'9') ch=getchar();
39 while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
40 return x;
41 }
42
43 void DFS_1(int x,int ff,int layer){
44 fa[x]=ff,dep[x]=layer,size[x]=1,gonxt[x]=0;
45 for (int j=G.lnk[x]; j; j=G.nxt[j]) if (G.son[j]!=ff){
46 DFS_1(G.son[j],x,layer+1),size[x]+=size[G.son[j]],wtofa[G.son[j]].x=G.w[j];
47 if (size[gonxt[x]]<size[G.son[j]]) gonxt[x]=G.son[j];
48 }
49 }
50
51 void DFS_2(int x,int ff){
52 pos[x]=++cloc,who[cloc]=x;
53 if (gonxt[x]) top[gonxt[x]]=top[x],bel[gonxt[x]]=bel[x],DFS_2(gonxt[x],x),num[x]+=num[gonxt[x]]; else num[x]=1;
54 for (int j=G.lnk[x]; j; j=G.nxt[j]) if (G.son[j]!=ff&&G.son[j]!=gonxt[x])
55 top[G.son[j]]=G.son[j],bel[G.son[j]]=++cnt,DFS_2(G.son[j],x);
56 }
57
58 void Update(int now,int L,int R,int aim,int key){
59 if (L>R) return;
60 if (L==aim&&R==aim){
61 T[now].key=key,T[now].Toge^=key; return;
62 }else if (L==R) return;
63 if (mid>=aim) Update(now<<1,L,mid,aim,key);
64 else Update(now<<1|1,mid+1,R,aim,key);
65 T[now].Toge=T[now<<1].Toge^T[now<<1|1].Toge;
66 }
67
68 int Query(int now,int L,int R,int aimL,int aimR){
69 if (L>aimR||R<aimL) return 0;
70 if (L>=aimL&&R<=aimR) return T[now].Toge;
71 if (mid>=aimR) return Query(now<<1,L,mid,aimL,aimR);
72 else if (mid<aimL) return Query(now<<1|1,mid+1,R,aimL,aimR);
73 else return Query(now<<1,L,mid,aimL,aimR)^Query(now<<1|1,mid+1,R,aimL,aimR);
74 }
75
76 int answer(int x,int y){
77 int ret=0;
78 while (bel[x]!=bel[y]){
79 if (dep[top[x]]>dep[top[y]]) ret^=Query(1,1,n,pos[top[x]],pos[x]),x=fa[top[x]];
80 else ret^=Query(1,1,n,pos[top[y]],pos[y]),y=fa[top[y]];
81 }
82 if (dep[x]<dep[y]) swap(x,y);
83 ret^=Query(1,1,n,pos[y]+1,pos[x]);
84 return ret;
85 }
86
87 int main(){
88 for (int Ts=read(); Ts; Ts--){
89 n=read(),G.clear();
90 M(T); M(wtofa); M(que);
91 for (int i=1; i<n; i++){
92 int x=read(),y=read(),z=read();
93 G.add(x,y,z); G.add(y,x,z);
94 }
95 DFS_1(1,0,1);
96 wtofa[1].x=0;
97 for (int i=1; i<=n; i++) wtofa[i].i=i;
98 sort(wtofa+1,wtofa+1+n);
99 bel[1]=cnt=top[1]=1;
100 DFS_2(1,0);
101 Q=read();
102 for (int i=1; i<=Q; i++) que[i].x=read(),que[i].y=read(),que[i].z=read(),que[i].i=i;
103 sort(que+1,que+1+Q);
104 int j=1;
105 for (int i=1; i<=Q; i++){
106 while (wtofa[j].x<=que[i].z&&j<=n) Update(1,1,n,pos[wtofa[j].i],wtofa[j].x),j++;
107 finalans[que[i].i]=answer(que[i].x,que[i].y);
108 }
109 for (int i=1; i<=Q; i++) printf("%d\n",finalans[i]);
110 }
111 return 0;
112 }
