lg2420[边权]

链接:lg2420[边权]

题解

  • 和维护点权差不多,脑洞yy一下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    using namespace std;
    const int N=1e6;
    ll rt[N],lz[N],deep[N],size[N],hson[N],f[N],top[N],id[N];
    ll head[N],nxt[N],to[N],w[N],wt[N],wc[N];
    int cnt,n,m;
    inline void adde(int u,int v,int x){nxt[++cnt]=head[u];to[cnt]=v;wt[cnt]=x;head[u]=cnt;}
    inline void pushup(int o){rt[o]=rt[o<<1]^rt[o<<1|1];}
    inline void build(int o,int l,int r){
    if(l==r){rt[o]=w[l];return ;}
    int mid=l+r>>1;
    build(lson);
    build(rson);
    pushup(o);
    }
    inline ll query(int o,int l,int r,int L,int R){
    if(L<=l&&R>=r)return rt[o];
    int mid=l+r>>1;
    ll ans=0;
    if(L<=mid){ll tp=query(lson,L,R);if(!ans)ans=tp;else ans^=tp;}
    if(R>mid){ll tp=query(rson,L,R);if(!ans)ans=tp;else ans^=tp;}
    return ans;
    }
    inline void dfs1(int x){
    size[x]=1;
    for(int i=head[x];i;i=nxt[i])if(to[i]!=f[x]){
    wc[to[i]]=wt[i];
    f[to[i]]=x;
    deep[to[i]]=deep[x]+1;
    dfs1(to[i]);
    size[x]+=size[to[i]];
    if(size[hson[x]]<size[to[i]])hson[x]=to[i];
    }
    }
    inline void dfs2(int x,int t){
    top[x]=t;id[x]=++cnt;w[cnt]=wc[x];
    if(hson[x])dfs2(hson[x],t);
    for(int i=head[x];i;i=nxt[i])if(to[i]!=hson[x]&&to[i]!=f[x])dfs2(to[i],to[i]);
    }
    inline ll queryrange(int x,int y){
    ll ans=0;
    while(top[x]!=top[y]){
    if(deep[top[x]]<deep[top[y]])swap(x,y);
    ll tp=query(1,1,n,id[top[x]],id[x]);
    if(!ans)ans=tp;else ans^=tp;
    x=f[top[x]];
    }
    if(x==y)return ans;
    if(deep[x]>deep[y])swap(x,y);
    return ans^query(1,1,n,id[hson[x]],id[y]);
    }


    int main(){
    scanf("%d",&n);
    rep(i,2,n){
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);
    adde(x,y,z);adde(y,x,z);
    }cnt=0;
    dfs1(1);
    dfs2(1,1);
    build(1,1,n);
    scanf("%d",&m);
    while(m--){
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%lld\n",queryrange(x,y));
    }
    return 0;
    }