官方题解——异或生成树

C - 异或生成树

树型 $dp$

$dp[i][j]$ 表示以 $i$ 为根的子树能否组成 $j$ ，如果为 $1$ 可以组成，如果为 $0$ 无法组成。由于是异或操作，所以 $j$ 的范围是 $0-127$ 。转移方程为 $dp[i][k \oplus t] = dp[i][k] \& dp[j][t]$ （ $j$ 为 $i$ 的子节点）；

从根 $1$ 开始 $dfs$ 遍历每一个子节点，每遍历完一个子节点更新一下当前节点的 $dp$ 值。

队友的代码：

#include <bits/stdc++.h>
#include <cstring>
using namespace std;
#define MAXN 103
#define MAXM 203
#define debug 0

int sum = 0;
int ans,edgesize;
int a[MAXN],g[MAXN];
int dp[MAXN][130],res[130];
struct edge
{
    int f,t;
    void var(int _f,int _t)
    {
        f = _f;
        t = _t;
    }
}edges[MAXM];
void addedge(int f,int t)
{
    edges[++edgesize].var(g[f],t);
    g[f] = edgesize;
}
void solve(int now,int pre)
{
    //printf("%d\n",now);
    dp[now][a[now]] = 1;
    ans = max(ans,a[now]);
    for(int i = g[now];~i;i = edges[i].f)
    {
        if(edges[i].t == pre)
            continue;
        solve(edges[i].t,now);
        for(int j = 0;j <= 127;j++)
            res[j] = 0;
        for(int j = 0;j <= 127;j++)
            if(dp[edges[i].t][j])
                for(int k = 0;k <= 127;k++)
                {
                    if(dp[now][k])
                    {
                        res[k ^ j] = 1;
                        ans = max(ans,k ^ j);
                    }
                }
        for(int j = 0;j <= 127;j++)
            dp[now][j] |= res[j];

    }
}
int main()
{
    int n,u,v;
    int ans_num = 0;
    int now = 0;
    //freopen("1.in","r",stdin);
    scanf("%d",&n);
    memset(g,-1,sizeof(g));
    memset(dp,0,sizeof(dp));
    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    edgesize = 0;
    for(int i = 1;i < n;i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    ans = 0;
    solve(1,0);
    printf("%d\n",ans);
    #if debug
    for(int i = 1;i <= n;i++)
    {
        printf("%d: ",i);
        for(int j = 0;j <= 128;j++)
            if(dp[i][j])
                printf("%d ",j);
        printf("\n");
    }
    #endif
    //printf("T:%d\n",ans_num);
    return 0;
}