hdu 5416 CRB and Tree ( 2015 多校 #10 )
http://acm.hdu.edu.cn/showproblem.php?pid=5416
题意：给出一棵树（n<=1E5），定义二元函数函数f(u,v) (u可以等于v)表示节点u到节点v经过的路径的权值的异或和。给出q组查询（q<=10），每组一个s,问有多少对无序点对（u,v）满足f(u,v)=s. 思路：类似codeforces #340 div 2 E XOR and Favorite Number 先dfs,处理出从根节点都任意节点的异或前缀和。然后对于每个询问o(n)扫一遍，统计sum[i]^s出现多少次。 总的时间复杂度为O(Tqn);
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月19日 星期五 13时52分32秒
4File Name :code/hdu/5416.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,LL >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34vector<pi>edge[N];
35int n;
36LL sum[N];
37LL cnt[N*10];
38int q;
39void dfs( int x,LL val)
40{
41 sum[x] = val;
42
43 for ( int i = 0 ; i< edge[x].size() ; i++)
44 {
45 pi v = edge[x][i];
46 if (sum[v.fst]!=-1) continue ; //表示已经访问过了。
47 dfs(v.fst,val^v.sec);
48 }
49}
50
51LL cal( LL x)
52{
53 LL res = 0 ;
54 for ( int i = 1 ; i <= n ; i++)
55 {
56 res +=cnt[sum[i]^x];
57// cout<<"i:"<<i<<" res:"<<res<<endl;
58 }
59 if (x==0) res +=n; //f(u,u)
60
61 res /=2; //因为要求无序。。。 （u,v）和(v,u)算一种。
62 return res;
63}
64int main()
65{
66 #ifndef ONLINE_JUDGE
67 freopen("code/in.txt","r",stdin);
68 #endif
69 int T;
70 cin>>T;
71 while (T--)
72 {
73
74 scanf("%d",&n);
75 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
76 for ( int i = 1 ; i <= n-1 ; i++)
77 {
78 int a,b,c;
79 scanf("%d %d %d",&a,&b,&c);
80 edge[a].push_back(make_pair(b,c));
81 edge[b].push_back(make_pair(a,c));
82 }
83 ms(sum,-1);
84 dfs(1,0);
85 ms(cnt,0);
86// for ( int i = 1 ; i <= n ; i++) cout<<"sum[i]:"<<sum[i]<<endl;
87 for ( int i = 1 ; i <= n ; i++)
88 if (sum[i]>=0)
89 cnt[sum[i]]++;
90
91
92 scanf("%d",&q);
93 while (q--)
94 {
95 LL s;
96 scanf("%lld",&s);
97 LL ans = cal(s);
98 printf("%lld\n",ans);
99 }
100
101 }
102
103 #ifndef ONLINE_JUDGE
104 fclose(stdin);
105 #endif
106 return 0;
107}