[atAGC052B]Tree Edges XOR

定义两点的距离$d(x,y)$为$x$到$y$路径上边权异或和，则两棵树相同当且仅当$\forall 1\le i\le n$，$d(1,i)$相同

新建一个节点0，连边$(0,1)$，初始权值为0，且不能以这条边为对象操作（但操作与1相连的边会影响其）

记$d_{i}=d(0,i)$，考虑一次操作$(x,y)$对$d_{i}$的影响，恰好是交换$d_{x}$和$d_{y}$

最终，令$a_{i}$为目标树中$d(1,i)$的值，即要求$d_{i}\oplus d_{1}=a_{i}$

同时，记$b_{i}$为初始树中$d(0,i)$的值（也即$d(1,i)$），那么$d_{i}$即$b_{i}$重新排列的结果，有$\bigoplus_{i=1}^{n}d_{i}=\bigoplus_{i=1}^{n}b_{i}$

将之代入前者，根据$n$为奇数，可得$d_{1}=\bigoplus_{i=1}^{n}a_{i}\bigoplus_{i=1}^{n}b_{i}$，再判定$d_{1}$是否在本来的$b_{i}$中，以及$b_{i}\oplus d_{1}$是否等于$a_{i}$（排序后的结果）即可

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 struct Edge{

 5     int nex,to,len1,len2;

 6 }edge[N<<1];

 7 int E,n,x,y,z1,z2,head[N],a[N],b[N];

 8 void add(int x,int y,int z1,int z2){

 9     edge[E].nex=head[x];

10     edge[E].to=y;

11     edge[E].len1=z1;

12     edge[E].len2=z2;

13     head[x]=E++;

14 }

15 void dfs(int k,int fa,int s1,int s2){

16     b[k]=s1;

17     a[k]=s2;

18     for(int i=head[k];i!=-1;i=edge[i].nex)

19         if (edge[i].to!=fa)dfs(edge[i].to,k,s1^edge[i].len1,s2^edge[i].len2);

20 }

21 int main(){

22     scanf("%d",&n);

23     memset(head,-1,sizeof(head));

24     for(int i=1;i<n;i++){

25         scanf("%d%d%d%d",&x,&y,&z1,&z2);

26         add(x,y,z1,z2);

27         add(y,x,z1,z2);

28     }

29     dfs(1,0,0,0);

30     for(int i=1;i<=n;i++)b[0]^=a[i];

31     for(int i=1;i<=n;i++)b[0]^=b[i];

32     for(int i=1;i<=n;i++)b[i]^=b[0];

33     sort(a+1,a+n+1);

34     sort(b+1,b+n+1);

35     if (b[1]){

36         printf("NO");

37         return 0;

38     }

39     for(int i=1;i<=n;i++)

40         if (a[i]!=b[i]){

41             printf("NO");

42             return 0;

43         }

44     printf("YES");

45 }

巴特西

[atAGC052B]Tree Edges XOR

最新文章

热门文章