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

Posted by 111qqz on Friday, February 19, 2016

TOC

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
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,LL >
#define MP make_pair

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

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

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

    res /=2; //因为要求无序。。。 (u,v)和(v,u)算一种。
    return res;
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    int T;
    cin>>T;
    while (T--)
    {
	    
        scanf("%d",&n);
        for ( int i = 1 ; i <= n ; i++) edge[i].clear();
        for ( int i = 1 ; i <= n-1 ; i++)
        {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        edge[a].push_back(make_pair(b,c));
        edge[b].push_back(make_pair(a,c));
        }
        ms(sum,-1);
        dfs(1,0);
        ms(cnt,0);
//	    for ( int i = 1 ;  i <= n ; i++) cout<<"sum[i]:"<<sum[i]<<endl;
        for ( int i = 1 ; i <= n ; i++)
        if (sum[i]>=0)
        cnt[sum[i]]++;
	    
	    
        scanf("%d",&q);
        while (q--)
        {
        LL s;
        scanf("%lld",&s);
        LL ans = cal(s);
        printf("%lld\n",ans);
        }
	    
    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付