P14755 题解

· · 题解

虽然异或有很多高级的用法，但对于此题我们只需要知道任何数异或 0 后等于它本身，异或它自己后等于 0。

我们想要让 a_i = i 只能将它先异或上自己，但是这样会让其子树上的数也异或上 a_i 考虑怎么消除即在不影响 i 本身的情况下让它子树上的数再异或一次 a_i。

由此我们可以得出一个构造。对于连接奇数条边的点，设它连接的点为 j，只需要对于所有 j 进行 j，i 操作。此时对于 i 一共进行奇数次异或最终值为 a_i，对于它连接的点减去它为根的那一次进行了偶数次操作，最终值为 0。相似的，连接偶数条边的点则相反，除了它本身为 0 外其他点都是 a_i，只需再进行 i，i 操作就行。显然这样操作的次数不超过 3n 次。

代码

#include<bits/stdc++.h>
const int maxn=200005;
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
    return x*f;
}
int n;
int head[maxn],cnt;
struct nm{int to,next;}pa[maxn<<1];
void add(int u,int v){
    pa[++cnt].next = head[u];
    pa[cnt].to = v;
    head[u] = cnt;
}
int tot[maxn],sum;
void dfs(int now,int fa){
    for(int i=head[now];i;i=pa[i].next){
        int nx=pa[i].to; 
        tot[now]++;
        if(nx==fa) continue;
        dfs(nx,now);
    }
    if(tot[now]%2) sum+=tot[now];
    else sum+=tot[now]+1;
}
signed main(){
    int T=read();
    while(T--){
        n=read();
        memset(tot,0,sizeof(tot));
        memset(head,0,sizeof(head));
        cnt=0;sum=0;    
        for(int i=1;i<n;i++){
            int u=read(),v=read();
            add(u,v);
            add(v,u);
        }
        dfs(1,1);
        cout<<sum<<endl;
        for(int i=1;i<=n;i++){
            for(int j=head[i];j;j=pa[j].next){
                int nx=pa[j].to;
                cout<<nx<<' '<<i<<endl;
            }
            if(!(tot[i]%2)) cout<<i<<' '<<i<<endl;
        }
    }
    return 0;
}
/*
1
6
2 5
5 3
3 1
1 4
1 6
*/