P8200 题解

MeowScore · 2022-03-12 21:38:39 · 题解

传送门 qwq

这是一道黄题，显然出题人想让我们用很简单的办法秒掉这道题，所以我使用树剖套线段树。

考虑异或的性质，如果一条边的权值被异或两遍，就相当于没异或。

再来看这道题。对于一次询问 (x,y,k)，我们任取一个点 t，如果 t 不在 x 到 y 的链上，设沿着 t 向上或向下走，首次到达 x 到 y 的链上时处于点 p，则：

如果 t 在 x 到 y 的链上，显然：

发现柿子是一样的。

于是发现对于这个查询，我们只要判断 x 到 y 这条链上的异或和是否等于 k 就好了。树剖套线段树，线段树维护区间异或和即可。

代码：

#include<bits/stdc++.h>
using namespace std;
unsigned long long read(){
    unsigned long long ss=0,ww=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            ww=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        ss=ss*10+ch-'0';
        ch=getchar();
    }
    return ss*ww;
}
int readi(){
    int ss=0,ww=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            ww=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        ss=ss*10+ch-'0';
        ch=getchar();
    }
    return ss*ww;
}
int n,m;
const int N=500010;
int head[N],nex[N*2],to[N*2],cnt;
unsigned long long e[N*2];
void add(int x,int y,unsigned long long z){
    cnt++;
    nex[cnt]=head[x];
    to[cnt]=y;
    e[cnt]=z;
    head[x]=cnt;
}
unsigned long long a[N],t[N];
unsigned long long st[N*4];
int sz[N],son[N],tp[N],fa[N],dfn[N],dep[N],tot;
void dfs1(int x,int f){
    fa[x]=f;
    dep[x]=dep[fa[x]]+1;
    sz[x]=1;
    int maxn=-1;
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)
            continue;
        t[y]=e[i];
        dfs1(y,x);
        sz[x]+=sz[y];
        if(sz[y]>maxn){
            maxn=sz[y];
            son[x]=y;
        }
    }
}
void dfs2(int x,int top){
    tp[x]=top;
    tot++;
    dfn[x]=tot;
    a[tot]=t[x];
    if(son[x])
        dfs2(son[x],top);
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])
            continue;
        dfs2(y,y);
    }
}
unsigned long long res;
void build(int root,int l,int r){
    if(l==r){
        st[root]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    st[root]=st[root*2]^st[root*2+1];
}
void ask(int root,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        res=(res^st[root]);
        return;
    }
    int mid=(l+r)/2;
    if(mid>=x)
        ask(root*2,l,mid,x,y);
    if(mid+1<=y)
        ask(root*2+1,mid+1,r,x,y);
}
int main(){
    n=readi();
    m=readi();
    for(int i=1;i<n;i++){
        int x,y;
        unsigned long long z;
        x=readi();
        y=readi();
        z=read();
        add(x,y,z);
        add(y,x,z);
    }
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int x,y;
        unsigned long long k;
        x=readi();
        y=readi();
        k=read();
        res=0;
        while(tp[x]!=tp[y]){
            if(dep[tp[x]]<dep[tp[y]])
                swap(x,y);
            ask(1,1,n,dfn[tp[x]],dfn[x]);
            x=fa[tp[x]];
        }
        if(x!=y){
            if(dep[x]>dep[y])
                swap(x,y);
            ask(1,1,n,dfn[x]+1,dfn[y]);
        }
        if(res==k)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}