HDU 5416 CRB and Tree （技巧）

题意：给一棵n个节点的树（无向边），有q个询问，每个询问有一个值s，问有多少点对(u,v)的xor和为s？注意：(u,v)和(v,u)只算一次。而且u=v也是合法的。

思路：任意点对之间的路径肯定经过LCA的，但是如果如果知道某个点t到根的路径xor和为e，那么就能够得知 x^e=s中的x应该是多少，那就算有多少点到根的xor和为x即可。e是表示t到根的，所以而x也是其他点到根的路径xor和，两个点他们的LCA到根这段会被算2次，那么xor就为0了。

　　（1）DFS算出每个点到根的路径xor和，相同的用一个桶装起来，复杂度O(n)。

　　（2）对于每个询问s，穷举树上n个点，找到另一个点到root的路径xor和，在对应桶里的都是可以组成s的。（注意要去重）

　　特别要注意的是，s可能为0，那么就有x^x=s的情况，另一个点也会在同一个桶里。还有，要用long long保存答案。

 #include <bits/stdc++.h>

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 #define LL long long

 using namespace std;

 const int N=;

 vector<int> vect[N];

 struct node

 {

     int from,to,val;

     node(){};

     node(int from,int to,int val):from(from),to(to),val(val){};

 }edge[N*];

 int edge_cnt, n, buck[N*], self[N], vis[N], q;

 void add_node(int from,int to,int val)

 {

     edge[edge_cnt]=node(from, to, val);

     vect[from].push_back(edge_cnt++);

 }

 void DFS(int x,int sum)

 {

     vis[x]=;

     for(int i=; i<vect[x].size(); i++)

     {

         node &e=edge[vect[x][i]];

         if( !vis[e.to])

         {

             buck[ self[e.to]=sum^e.val ]++;

             DFS(e.to, sum^e.val);

         }

     }

 }

 LL get_ans(int a)

 {

     LL ans=;

     if(a==)

     {

         for(int j=; j<=n; j++)

         {

             int t=self[j];          //a为0，这个桶肯定是自己的那个

             ans+=buck[ t ]-;       //先扣掉自己。但是仍然会算重了。它到别人，别人也会到他。

         }

         ans+=n*; //每个点到自己都算。

     }

     else        //a!=0，那么不可能有两个相同数的异或和为a的。

     {

         for(int j=; j<=n; j++)

         {

             int t=a^self[j];    //这个肯定不跟j同个桶。

             ans+=buck[t];

         }

     }

     return ans/;   //去重

 }

 void cal(int n)

 {

     memset(vis, , sizeof(vis));

     memset(buck, , sizeof(buck));

     memset(self, , sizeof(self));

     DFS(, );

     cin>>q;

     for(int i=,a=; i<q; i++)

     {

         scanf("%d", &a);

         printf("%lld\n", get_ans(a));

     }

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int t, a, b, c;

     cin>>t;

     while(t--)

     {

         cin>>n;

         edge_cnt=;

         for(int i=; i<=n; i++) vect[i].clear();

         for(int i=; i<n; i++)

         {

             scanf("%d%d%d", &a, &b, &c);

             add_node(a,b,c);

             add_node(b,a,c);

         }

         add_node(, , );  //虚拟的根节点，0号节点

         cal(n);

     }

     return ;

 }

AC代码

数据

3
1 2 1
2 3 2
3
2
3
4

4
1 2 1
2 3 2
2 4 1
4
0
1
2
3

答案：

1
1
0
5
2
1
2

巴特西

HDU 5416 CRB and Tree （技巧）

最新文章

热门文章