hdu 5416 CRB and Tree ( 2015 多校 #10 )

2016-02-19 · 2 min read · dfs 前缀和

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);

/* ***********************************************
Author :111qqz
Created Time :2016年02月19日 星期五 13时52分32秒
File Name :code/hdu/5416.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,LL >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E5+7;
 7vector<pi>edge[N];
 8int n;
 9LL sum[N];
10LL  cnt[N*10];
11int q;
12void dfs( int x,LL val)
13{
14    sum[x] = val;

1    for ( int i = 0 ; i< edge[x].size() ; i++)
2    {
3	pi v = edge[x][i];
4	if (sum[v.fst]!=-1) continue ; //表示已经访问过了。
5	dfs(v.fst,val^v.sec);
6    }
7}

1LL cal( LL x)
2{
3    LL res = 0 ;
4    for ( int i = 1 ; i <= n ; i++)
5    {
6	res +=cnt[sum[i]^x];
7//	cout<<"i:"<<i<<" res:"<<res<<endl;
8    }
9    if (x==0) res +=n; //f(u,u)

 1    res /=2; //因为要求无序。。。 （u,v）和(v,u)算一种。
 2    return res;
 3}
 4int main()
 5{
 6	#ifndef  ONLINE_JUDGE 
 7	freopen("code/in.txt","r",stdin);
 8  #endif
 9	int T;
10	cin>>T;
11	while (T--)
12	{

 1	    scanf("%d",&n);
 2	    for ( int i = 1 ; i <= n ; i++) edge[i].clear();
 3	    for ( int i = 1 ; i <= n-1 ; i++)
 4	    {
 5		int a,b,c;
 6		scanf("%d %d %d",&a,&b,&c);
 7		edge[a].push_back(make_pair(b,c));
 8		edge[b].push_back(make_pair(a,c));
 9	    }
10	    ms(sum,-1);
11	    dfs(1,0);
12	    ms(cnt,0);
13//	    for ( int i = 1 ;  i <= n ; i++) cout<<"sum[i]:"<<sum[i]<<endl;
14	    for ( int i = 1 ; i <= n ; i++)
15		if (sum[i]>=0)
16		cnt[sum[i]]++;

1	    scanf("%d",&q);
2	    while (q--)
3	    {
4		LL s;
5		scanf("%lld",&s);
6		LL ans = cal(s);
7		printf("%lld\n",ans);
8	    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}