HDU 5416 CBR and tree

#include<bits/stdc++.h>

using namespace std;

#define for(i,a,b) for(int i=a;i<=b;++i)

//T,N,Q,,u,v,w,s,tree[maxn][?],val[maxn],cashbook[maxn*2],ans

const int maxn=1e5+5;

struct node

{

    int i,v;

    node(){}

    node(int a,int b){i=a,v=b;}

};

vector<node> tree[maxn];

int val[maxn],cashbook[2*maxn],s;

long long ans;

void dfs(int i,int p)

{

    //record in cashbook[]

    cashbook[val[i]]++;

    //renew ans;

    ans+=cashbook[s^val[i]];

    //move to sons, cal their value

    int nei=tree[i].size();

    for(j,0,nei-1)

    {

        int name=tree[i][j].i;

        if(name==p)continue;

        val[name]=val[i]^tree[i][j].v;

        dfs(name,i);

    }

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        //construct the tree

        int N,u,v,w;scanf("%d",&N);

        for(i,1,N)tree[i].clear();

        for(i,1,N-1)

        {

            scanf("%d%d%d",&u,&v,&w);

            tree[u].push_back(node(v,w));

            tree[v].push_back(node(u,w));

        }

        //query

        int Q;scanf("%D",&Q);

        while(Q--)

        {

            memset(cashbook,0,sizeof cashbook);

            memset(val,0,sizeof val);

            ans=0;

            scanf("%d",&s);

            dfs(1,0);

            //print ans

            printf("%lld\n",ans);

        }

    }

}
巴特西

HDU 5416 CBR and tree

最新文章

热门文章
