[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)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define M(A) memset(A,0,sizeof A);
#define mid ((L+R)>>1)
using namespace std;
const int maxn=100005,maxe=200005;

int n,Q,fa[maxn],dep[maxn],size[maxn],gonxt[maxn];
int top[maxn],bel[maxn],num[maxn],cnt;
int pos[maxn],who[maxn],cloc;
int finalans[100005];

struct weight{
    int x,i;
    bool operator < (const weight &other) const {return x<other.x;}
}wtofa[maxn];

struct segment_tree{
    int Toge,key;
}T[maxn*20];

struct edge{
    int nxt[maxe],son[maxe],w[maxe],lnk[maxn],tot;
    bool cmp(edge &x,edge &y){return x.w<y.w;} 
    void clear(){tot=cnt=cloc=0; M(nxt); M(son); M(w); M(lnk); M(gonxt);}
    void add(int x,int y,int z){nxt[++tot]=lnk[x],son[tot]=y,w[tot]=z,lnk[x]=tot;}
}G;

struct queries{
    int x,y,z,i;
    bool operator < (const queries &other) const {return z<other.z;}
}que[100005];

inline int read(){
    int x=0; char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}

void DFS_1(int x,int ff,int layer){
    fa[x]=ff,dep[x]=layer,size[x]=1,gonxt[x]=0;
    for (int j=G.lnk[x]; j; j=G.nxt[j]) if (G.son[j]!=ff){
        DFS_1(G.son[j],x,layer+1),size[x]+=size[G.son[j]],wtofa[G.son[j]].x=G.w[j];
        if (size[gonxt[x]]<size[G.son[j]]) gonxt[x]=G.son[j];
    }
}

void DFS_2(int x,int ff){
    pos[x]=++cloc,who[cloc]=x;
    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;
    for (int j=G.lnk[x]; j; j=G.nxt[j]) if (G.son[j]!=ff&&G.son[j]!=gonxt[x])
    top[G.son[j]]=G.son[j],bel[G.son[j]]=++cnt,DFS_2(G.son[j],x);
}

void Update(int now,int L,int R,int aim,int key){
    if (L>R) return;
    if (L==aim&&R==aim){
        T[now].key=key,T[now].Toge^=key; return;
    }else if (L==R) return;
    if (mid>=aim) Update(now<<1,L,mid,aim,key);
    else Update(now<<1|1,mid+1,R,aim,key);
    T[now].Toge=T[now<<1].Toge^T[now<<1|1].Toge;
}

int Query(int now,int L,int R,int aimL,int aimR){
    if (L>aimR||R<aimL) return 0;
    if (L>=aimL&&R<=aimR) return T[now].Toge;
    if (mid>=aimR) return Query(now<<1,L,mid,aimL,aimR);
    else if (mid<aimL) return Query(now<<1|1,mid+1,R,aimL,aimR);
    else return Query(now<<1,L,mid,aimL,aimR)^Query(now<<1|1,mid+1,R,aimL,aimR);
}

int answer(int x,int y){
    int ret=0;
    while (bel[x]!=bel[y]){
        if (dep[top[x]]>dep[top[y]]) ret^=Query(1,1,n,pos[top[x]],pos[x]),x=fa[top[x]];
        else ret^=Query(1,1,n,pos[top[y]],pos[y]),y=fa[top[y]];
    }
    if (dep[x]<dep[y]) swap(x,y);
    ret^=Query(1,1,n,pos[y]+1,pos[x]);
    return ret;
}

int main(){
    for (int Ts=read(); Ts; Ts--){
        n=read(),G.clear();
        M(T); M(wtofa); M(que);
        for (int i=1; i<n; i++){
            int x=read(),y=read(),z=read();
            G.add(x,y,z); G.add(y,x,z);
        }
        DFS_1(1,0,1);
        wtofa[1].x=0;
        for (int i=1; i<=n; i++) wtofa[i].i=i;
        sort(wtofa+1,wtofa+1+n);
        bel[1]=cnt=top[1]=1;
        DFS_2(1,0);
        Q=read(); 
        for (int i=1; i<=Q; i++) que[i].x=read(),que[i].y=read(),que[i].z=read(),que[i].i=i;
        sort(que+1,que+1+Q);
        int j=1;
        for (int i=1; i<=Q; i++){
            while (wtofa[j].x<=que[i].z&&j<=n) Update(1,1,n,pos[wtofa[j].i],wtofa[j].x),j++;
            finalans[que[i].i]=answer(que[i].x,que[i].y);
        }
        for (int i=1; i<=Q; i++) printf("%d\n",finalans[i]);
    }
    return 0;
}