世界树的考验「NOIP多校联考 2019」

题意

有一颗带边权的树，每次操作可以将一条路径上所有边权同时异或一个任意值，求最少多少次操作可以将所有边权变为0。

（题目保证边权≤15）

思路

可以发现题目保证了边权，看到这个数字容易联想到状压（天知道为什么我没联想到）。

由于边权不是很好处理，所以我们可以将其转换到点上面去，那么每一个点的点权就是与之相连的边权异或值。

由于异或运算拥有自反性，所以原先路径的操作就相当于选取两个点，同时异或一个值。（路径中间的每一个点都被异或两次，相当于没有被异或）

很显然相同权值的点可以两两一对先消掉，然后再考虑剩下的节点。

那么我们设子状态\(dp[s]\)表示将状态s消除所需的最小操作次数。（由于相同权值被两两消除，所以每一位最多为1）

转移过程是显然的。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

    template<typename T>inline void read (T &x) {
        x=0;T f=1;char c=getchar();
        for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
        for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
        x*=f;
    }

    template<typename T>inline void write (T x) {
        if (x<0) putchar('-'),x*=-1;
        if (x>=10) write(x/10);
        putchar(x%10+'0');
    }

}

using namespace StandardIO;

namespace Project {
    
    const int N=100100;
    const int INF=2147483647;
    
    int n,ans,S;
    int v[N],cnt[16];
    int dp[(1<<16)];
    
    int dfs (int s) {
        if (!s) return 0;
        if (dp[s]<INF) return dp[s];
        for (register int i=0; i<16; ++i) {
            if (!((s>>i)&1)) continue;
            for (register int j=0; j<16; ++j) {
                if (!((s>>j)&1)) continue;
                if (i==j) continue;
                int p=i^j,x=(s-(1<<i)-(1<<j))^(1<<p);
                if ((s>>p)&1) dp[s]=min(dp[s],dfs(x)+2);
                else dp[s]=min(dp[s],dfs(x)+1);
            }
        }
        return dp[s];
    }

    inline void MAIN () {
        read(n);
        for (register int i=1,a,b,c; i<n; ++i) {
            read(a),read(b),read(c);
            v[a]^=c,v[b]^=c;
        }
        for (register int i=0; i<n; ++i) ++cnt[v[i]];
        for (register int i=1; i<16; ++i) ans+=(cnt[i]>>1),S|=(1<<i)*(cnt[i]&1);
        for (register int i=0; i<(1<<16); ++i) dp[i]=INF;
        write(ans+dfs(S));
    }
    
}

int main () {
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    Project::MAIN();
}

世界树的考验「NOIP多校联考 2019」

原文：https://www.cnblogs.com/ilverene/p/11619825.html