[codechef July Challenge 2017] Pishty and tree

[codechef July Challenge 2017] Pishty and tree

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&#[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&#[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("%dn",finalans[i]);
110     }
111     return 0;
112 }

转载于:.html