世界树的考验

题目大意:

终于，历经千难万险后，路明非来到了世界树下，探寻自己的身世之谜，但世界树却给他出了一道难题。
世界树是一个有n（n<=100000）个节点n-1条边组成的无向连通图，树上的每条边都有一个边权，路明非每次可以选中世界树上任意两个点，将其路径上所有边权（边权<=15）异或上同一个数，现在世界树想知道，路明非最少用多少次操作可以将所有边权变为0。
请你帮帮路明非，只有回答出世界树的问题，路明非才能知道自己的身世 .

题目思路：

 

首先，对题目进行预处理。

预处理1：将边权转换为点权

题目中要求让所有的边，异或之后全部变为0，我们可以将边权移到点权上，点权=与他相邻的所有边的权值的异或，所以当所有的边的边权都为0时，此时所有的点权也应该都为0，所以答案转换为每次使一条路径上的边都异或一个数C，最后使得所有的点权变为0.

预处理2：树上差分

如上图所示：

根据预处理1，用sz数组记录各点点权，那么：

sz[1]=2,sz[2]=2^1,sz[3]=1^1,sz[4]=1

假设我对这一条路径上的边都异或C，那么因为2连着两条边，所以2相当于没有异或。所以该操作，只对1和4进行了修改，也就是对路径进行修改，也就等于对该路径的终点和起点进行了修改。

所以题目转换成为：每次使得两个顶点异或上一个值，求最小的操作次数使得所有的值都变为0。

首先可以想到的是，如果两个相同先异或两个相同的。

所以我们首先每个权值的次数，除2下取整，就是首先要进行的异或对。

进行上述操作之后，要么没有点的权值是该权值，要么只有一个点的权值是该权值，我们的目的是使得所有点的权值为0.

所以我们用S>>i&1来判断，有没有点的权值是i

所以进行一个记忆化搜索的状压DP

因为我们每次选一对节点，即两个for循环遍历，一对节点，那么对于 一对权值 (i,j)，我们绝对要使得一个权值先消失(即异或i或者异或j），无论使得哪个权值先消失，都会产生一个新的权值 i^j(3 5 异或5 剩下3^5）。

所以这状态可以写为:

int p=i^j;
int x=S^(1<<i)^(1<<j)^(1<<p)//把i和j的影响取消，新来的有p的影响

然后，这时候我们需要考虑一下，S的p位是不是已经是1了，如果有1的话，我们上述操作其实已经执行了一次，就是默认将两个权值为p的异或了一下。

然后就是状态转移方程了(带有记忆化搜索)：

if(S>>p&1) //如果x的第p位已经是1了
    f[S]=min(f[S],dfs(x)+2);//相当于多执行了一次操作
else
    f[S]=min(f[S],dfs(x)+1);

AC代码(S和x交换了,写的时候没注意)：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=100000000000005;
const int maxn=1e6+5;
const int mod=1e9+7;
ll n,m;
ll f[maxn];//状压dp
ll sz[maxn];//每个节点权值
ll sum[20];//每个节点权值的数量
ll dfs(ll x)
{
    if(!x) return 0;
    if(f[x]<INF) return f[x];
    for(int i=1;i<16;i++)if((x>>i)&1)
    {
        for(int k=1;k<16;k++)if(i!=k&&(x>>k)&1)
        {
            int p=i^k;
            ll tempx=x^(1<<i)^(1<<k)^(1<<p);
            if(x>>p&1) f[x]=min(f[x],dfs(tempx)+2);
            else f[x]=min(f[x],dfs(tempx)+1);
        }
    }
    return f[x];
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n-1;i++)
    {
        ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);
        sz[a]^=c;
        sz[b]^=c;
    }
    ll res=0;
    ll S=0;
    for(int i=0;i<n;i++) sum[sz[i]]++;
    for(int i=1;i<=15;i++)
    {
        res+=sum[i]/2;
        if(sum[i]&1) S+=(1<<i);
    }
    for(int i=0;i<maxn;i++) f[i]=INF;
  //  printf("%lld\n",res);
    printf("%lld\n",dfs(S)+res);
    return 0;
}