P8200题解

__vector__ · 2022-06-14 16:25:16 · 个人记录

思路

分 t 在 a 到 b 的链上和 t 不在 a 到 b 的链上两种情况化简一下

• $dis_{a,t} \oplus dis_{t,b} = dis_{a,b}
• 因为 $dis_{t,lca(a,b)}$ 是 $t \rightarrow a$ 与 $t \rightarrow b$ 两条路径上重复的，被异或了两次，相当于没异或，实际上要计算的是：$dis_{a,lca(a,b)} \oplus dis_{lca(a,b),b} = dis_{a,b}

所以其实就是判断 dis_{a,b} 是否等于 k

另外要注意开 unsigned long long

代码

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef unsigned long long ull;
    const int maxn=5e5+5;
    int head[maxn];
    struct EDGE
    {
        int to,nxt;
        ull val;
    }edge[maxn<<1];
    int cnt=0;
    inline void add(int u,int to,ull val)
    {
        edge[++cnt].to=to;
        edge[cnt].val=val;
        edge[cnt].nxt=head[u];
        head[u]=cnt;
    }
    ull dis[maxn];
    int n,m;
    void dfs(int u,int fa)
    {
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(to==fa)continue;
            dis[to]=dis[u]^edge[i].val;
            dfs(to,u);
        }
    }
    ull get_dis(int x,int y)
    {
        return dis[x]^dis[y];
    }
    void main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<n;i++)
        {
            int x,y;
            ull l;
            scanf("%d%d%llu",&x,&y,&l);
            add(x,y,l);
            add(y,x,l);
        }
        dfs(1,0);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            ull k;
            scanf("%d%d%llu",&a,&b,&k);
            if(get_dis(a,b)==k)
            {
                printf("Yes\n");
            }
            else printf("No\n");
        }
;   }
}
int main()
{
    Main::main();
    return 0;
}