【题解】恢复森林

题意

给你一棵树每个节点上的度数，以及该节点与其相连的其他节点之间的异或和(与该节点相连的点的异或和,除该节点之外)，让你利用这些信息恢复出这棵树，输出这棵树的高度。

题解

首先可以发现的是，度数为一的点都是叶子节点。那么我们可以从叶子节点入手，可以发现叶子节点的异或值就是与该节点连接的节点编号。然后我们可以将该叶子节点删除，然后将与其相连的点的度数减一并且异或和异或上叶子节点的编号。重复这个操作再找到度数为的点，这样就可以恢复出整棵树，我们在删点的同时就可以知道当前叶子节点和什么点连接在一起也就获得了边的信息。利用边的信息就可以得到树的高度了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int deg[N],xo[N];
int vis[N];
queue<int>q;
vector<int>E[N];
int maxn=0;
void dfs(int u,int h)
{
    vis[u]=1;
    maxn=max(maxn,h);
    for(int i=0;i<E[u].size();i++)
    {
        if(!vis[E[u][i]])
            dfs(E[u][i],h+1);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d%d",&deg[i],&xo[i]);
        q.push(i);
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(deg[u]!=1)
            continue;
        deg[u]--;
        xo[xo[u]]^=u;
        deg[xo[u]]--;
        E[u].push_back(xo[u]);
        E[xo[u]].push_back(u);
        if(deg[xo[u]]==1)
            q.push(xo[u]);
    }
    dfs(0,1);
    printf("%d\n",maxn);
    return 0;
}