多校第十場 1011 hdu 5416 CRB and Tree(樹形dp)

#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#define MAX 100007

using namespace std;

typedef long long LL;
int t,n,q,s;
int dp[MAX];
vector<int> e[MAX];
vector<int> w[MAX];
LL mp[MAX*];

void add ( int u , int v , int x )
{
    e[u].push_back ( v );
    e[v].push_back ( u );
    w[u].push_back ( x );
    w[v].push_back ( x );
}

void dfs ( int u , int p )
{
    if ( p == - ) dp[u] = ;
    for ( int i =  ; i < e[u].size() ; i++ )
    {
        int v = e[u][i];
        int x = w[u][i];
        if ( v == p ) continue;
        dp[v] = dp[u]^x;
        dfs ( v , u );
    }
}

void init ( )
{
    for ( int i =  ; i < MAX ; i++ )
    {
        e[i].clear();
        w[i].clear();
    }
}

int main ( )
{
    scanf ( "%d" , &t );
    while ( t-- )
    {
        init ();
        scanf ("%d" , &n );
        int u,v,x;
        for ( int i =  ; i < n ; i++ )
        {
            scanf ("%d%d%d" , &u , &v , &x );
            add ( u , v , x );
        }
        dfs (  , - );
        scanf ( "%d" , &q );
        while ( q-- )
        {
            scanf ( "%d" , &s );
            memset ( mp ,  , sizeof ( mp ));
            LL ans = ;
            for ( int i =  ; i <= n ; i++ )
            {
                int x = s^dp[i];
                mp[dp[i]]++;
                ans += mp[x];
            }
            printf ( "%I64d\n" , ans );
        }
    }
}