【树上异或和计数】czr 太弱啦

【题目】：

　　给一棵树，求异或和为k的路径个数。

【题解】：

　　很遗憾比赛时做不出来，后来看别人题解做出来的。用于记录博客所用。

　　然后进行Dfs，得到从根节点到某一个节点的异或值，计算方案时只需要在map中查询

我们可以在

　　值得一提的是，题目保证了直径不超过150000，意在防止Dfs导致爆栈。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e6+10;
 4 typedef struct Edge{
 5     int to,next,w;
 6 }Edge;
 7 Edge e[N<<1];
 8 map<int,int>Mp;
 9 int head[N],cnt,n,m,k;
10 long long ans;
11 void add_edge(int u,int v,int w){
12     e[cnt] = Edge{ v ,head[u],w};
13     head[u] = cnt ++ ;
14 }
15 void dfs(int u,int fa,int w){
16     ans = ans + Mp[w^k];
17     Mp[w] ++ ;
18     for(int i=head[u];~i;i=e[i].next){
19         int to = e[i].to;
20         if( to == fa ) continue;
21         dfs( to , u , w^e[i].w );
22     }
23 }
24 int main()
25 {
26     memset(head,-1,sizeof head );
27     scanf("%d%d",&n,&k);
28     for(int i=1,u,v,w;i<n;i++){
29         scanf("%d%d%d",&u,&v,&w);
30         add_edge(u,v,w);
31         add_edge(v,u,w);
32     }
33     dfs(1,1,0);
34     printf("%lld
",ans);
35     return 0;
36 }

树上异或和为k的方案数

居然能让我找到一个类似的题目，真的太幸运了。

P2420 让我们异或吧

https://www.luogu.org/problem/P2420

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N = 1e5 + 100;
 6 typedef struct Edge{
 7     int to,next,w;
 8     //Edge() {}
 9     Edge( int To = 0 ,int Ne = -1 , int W = 0 ):
10     to(To) , next(Ne) , w(W) {}
11 }Edge;
12 Edge e[N<<1];
13 int head[N],dis[N],cnt;
14 void add_edge(int u,int v,int w){
15     e[cnt] = Edge( v,head[u],w);
16     head[u] = cnt ++ ;
17 }
18 
19 void dfs(int u,int Fa,int w){
20     dis[u] = w ;
21     for(int i=head[u];~i;i=e[i].next){
22         int to = e[i].to ;
23         if( to == Fa ) continue ;
24         dfs( to,u,w^e[i].w);
25     }
26 }
27 int main()
28 {
29     int n,m;
30     memset(dis,0,sizeof dis);
31     memset(head,-1,sizeof head);
32     scanf("%d",&n);
33     for(int i=1,u,v,w;i<n;i++){
34         scanf("%d%d%d",&u,&v,&w);
35         add_edge(u,v,w);
36         add_edge(v,u,w);
37     }
38     dfs(1,1,0);
39 
40     scanf("%d",&m);
41     for(int i=1,u,v;i<=m;i++){
42         scanf("%d%d",&u,&v);
43         int ans = dis[u] ^ dis[v] ;
44         printf("%d
",ans);
45     }
46 
47 }

P2420 让我们异或吧