The Best Path(欧拉+并查集)

# The Best Path

题意

给你n个点，m条边，问你是否能够一次性不重复的走完其他所有的边，对于每一点有一个权值，ans=经过的每一次点的异或和（一个点可以重复多次），求怎么走使得这个ans最大。

思路

一次性走完很显然是要欧拉路或者回路的，那么条件就是0个或者2个奇数度数的点，这个开头计数一下就好，另外还要判断是否连通，否则永远走不到某些路，所以用并查集查询father即可。

然后对于欧拉路来说，两个奇数度数的点一定有贡献，而对于偶数度数u的点来说，只要看u/2的奇偶性即可，是奇数就有贡献，偶数就没贡献，因此在开头把所有的点先异或一遍得一个ans，然后对于每一个点分析，如果没贡献就再异或一次。

如果是欧拉回路，那么就对每一个点作为起始点，我们可以发现起始点是没有贡献的，因此ans对于每一个起始点异或，取最大值即可。

看！代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=0x3f3f3f3f;
const int N = 100010;
int id[N];
int sz[N];

int poor[N];
int deg[N];
int Find(int x)  ///找跟根结点
{
    while(x!=id[x])
    {
        id[x]=id[id[x]];
        x=id[x];
    }
    return x;
}

int un(int p,int q)
{
    int pr=Find(p);
    int qr=Find(q);
    if(pr==qr) return -1;
    if(sz[pr]<=sz[qr])
    {
        sz[qr]+=sz[pr];id[pr]=qr;
    }
    else
    {
        sz[pr]+=sz[qr];id[qr]=pr;
    }
}

void clear()
{
    for(int i=1;i<=N;i++)
    {
        id[i]=i;sz[i]=1;
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        clear();
        memset(deg,0,sizeof(deg));
        int n,m;
        int ans=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&poor[i]);
            ans=ans^poor[i];
        }
        int u,v;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            deg[u]++;
            deg[v]++;
            un(u,v);
        }
        int ji=0,cnt=0;
        for(int i=1;i<=n;i++)
        {
             if(deg[i]&1) ji++;
             if(Find(i)!=Find(1))
             {
                 cnt++;break;
             }
        }
        if(cnt!=0||(ji!=0&&ji!=2)) {printf("Impossible\n");continue;}
        if(ji) //欧拉路
        {
           // cout<<ans<<endl;
            for(int i=1;i<=n;i++)
                if(deg[i]%2==0&&(deg[i]/2)%2==0)
                    ans=ans^poor[i];
        }
        else //回路
        {
            int temp;
            for(int i=1;i<=n;i++)
            {
                temp=ans^poor[i];
                ans=max(ans,temp);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}