HDU 5416 CRB and Tree(트리 DP)

제목 링크: 전송문
제목:
한 나무에 함수 F(u, v)를 주어 u에서 v까지의 경로의 변의 값이 다르거나 일어나는 결과를 표시한 다음에 F(u, v)=s가 몇 가지 상황이 있는지 구한다.
분석:
dp[u]를 설정하면 점 u가 루트 노드의 경로가 다르거나 일어나는 값을 표시하고 F(u, v)=dp[u]^dp[v]를 설정합니다. 우리는 cnt[x]를 설정하면 dp[u]=x의 상황이 몇 가지가 있는지 나타냅니다. 그러면 s가 0과 같지 않을 때 ans[s]=sigma(cnt[i]*cnt[s^i])를 표시하고 s=0의 상황을 주의하십시오.
코드는 다음과 같습니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

const int maxn = 1e6+10;

typedef long long LL;

int dp[maxn];

int head[maxn],ip;

LL cnt[maxn];

int n;

struct nod{
    int to,next,w;
}edge[maxn];

bool vis[maxn];
void init(){
    ip=0;
    memset(head,-1,sizeof(head));
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
}

void add(int u,int v,int w){
    edge[ip].to=v;
    edge[ip].w=w;
    edge[ip].next=head[u];
    head[u]=ip++;
}

int mmax;


void dfs(int u,int pre,int val){
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v= edge[i].to;
        if(v==pre) continue;
        if(edge[i].w^val>mmax)
            mmax = edge[i].w^val;
        cnt[edge[i].w^val]++;
        dfs(v,u,val^edge[i].w);
    }
}

int main()
{
    int t,m;
    scanf("%d",&t);
    while(t--){
        init();
        scanf("%d",&n);
        for(int i=0;i<n-1;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        mmax = 0;
        dfs(1,1,0);
        scanf("%d",&m);
        cnt[0]++;
        for(int i=0;i<m;i++){
            int s;
            scanf("%d",&s);
            LL ans = 0;
            for(int j=0;j<maxn;j++){
                if((s^j)==j) ans=ans+(cnt[j]*(cnt[j]-1));
                else ans = ans=ans+cnt[j]*cnt[s^j];
            }
            ans=ans/2;
            if(s==0) ans=ans+n;
            printf("%I64d
",ans);
        }
    }
    return 0;
}
/***
45
7
1 2 1
1 3 1
1 4 1
4 5 2
3 6 2
2 7 2
1123
1
2
3
0
**/