DTOJ3049 苋

• 題目
• • 題目描述
  • 輸入格式
  • 輸出格式
  • 樣例
  • • 樣例輸入
    • 樣例輸出
  • 資料範圍與提示
• 題解

題目

題目描述

衆所周知，一株馬齒苋是活的，當且僅當它是連通的

特别地，一株活馬齒苋上有 n n n個獨立的節點，以及連接配接這些點的 n − 1 n-1 n−1條苋邊。每條苋邊有一個值，定義為苋邊的鍵值

對于一株馬齒苋，我們定義兩點間的簡單路徑為其互相到達所經過的最短苋路徑

生物學界對于馬齒苋的性質有許多研究，其中生物學家

Pauling

在其 1995 1995 1995年的一篇論文中提到過這樣一個經典問題：給定一株馬齒苋上的一條簡單路徑，用生物方法判斷路徑上鍵值的異或和是否為 k k k

這裡嘗試對這個問題進行推廣，稱之為泛馬齒苋問題：給定一株馬齒苋，求有多少條簡單路徑，使得路徑上鍵值的異或和為 k k k

輸入格式

第一行，兩個整數 n , k n,k n,k

以下 n n n行 a , b , c a,b,c a,b,c表示 a → b a\rightarrow b a→b有邊，其鍵值為 c c c

輸出格式

一個數，即答案

樣例

樣例輸入

5 1
1 2 4
1 3 8
3 4 8
4 5 9
           

樣例輸出

1
           

資料範圍與提示

對于 30 % 30\% 30%的資料， 1 ⩽ n ⩽ 100 , k ⩽ 10 1\leqslant n\leqslant 100,k\leqslant10 1⩽n⩽100,k⩽10

對于 50 % 50\% 50%的資料， 1 ⩽ n ⩽ 2000 , k ⩽ 256 1\leqslant n\leqslant 2000,k\leqslant 256 1⩽n⩽2000,k⩽256

對于 100 % 100\% 100%的資料， 1 ⩽ n ⩽ 4 × 1 0 5 , k ⩽ 1 0 9 1\leqslant n\leqslant 4\times 10^5,k\leqslant 10^9 1⩽n⩽4×105,k⩽109

題解

由于這是一棵樹，是以簡單路徑就是沒有重複經過一個點的路徑

設 f ( u , v ) f(u,v) f(u,v)為從 u u u到 v v v的簡單路徑的異或和

由異或的性質： a ∧ a = 1 a\land a=1 a∧a=1可以知道， f ( u , v ) = f ( 1 , u ) ∧ f ( 1 , v ) f(u,v)=f(1,u)\land f(1,v) f(u,v)=f(1,u)∧f(1,v)

是以，我們可以先預處理出所有的 f ( 1 , u ) f(1,u) f(1,u)

又因為 a ∧ b = c a\land b=c a∧b=c可以推出 a ∧ c = b a\land c=b a∧c=b，是以，我們隻需要統計所有 f ( 1 , u ) ∧ k = f ( 1 , v ) f(1,u)\land k=f(1,v) f(1,u)∧k=f(1,v)的 u u u和 v v v就可以了

注意：用map離散化，答案要除以2

附上代碼：

#include<cstdio>
#include<map>
using namespace std;
map<int,int> d;
int n,k,tot,sum,head[400010],nxt[800010],to[800010],ver[800010],XOR[400010],s[400010];
long long ans;
void add(int u,int v,int w)
{
	nxt[++tot]=head[u],head[u]=tot,to[tot]=v,ver[tot]=w;
}
void dfs(int x,int fa)
{
	for(int i=head[x];i;i=nxt[i]) if(to[i]!=fa) XOR[to[i]]=XOR[x]^ver[i],dfs(to[i],x);
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1,u,v,w;i<n;i++) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
	dfs(1,0);
	for(int i=1;i<=n;i++) if(!d[XOR[i]]) d[XOR[i]]=++sum;
	for(int i=1;i<=n;i++) s[d[XOR[i]]]++;
	for(int i=1;i<=n;i++) ans+=s[d[XOR[i]^k]];
	printf("%lld",ans/2);
}