读题看懂样例就花了好久…
给一棵树,树上任意两个点的距离表示为距离%2,那这样任意两个点之间距离要不就是0要不就是1了,这样就能把树上的点分成两个集合,相同集合内点相距0,不同集合点相距1,然后推出公式就是 n + 6 ∗ ( C k 2 + C n − k 2 + C k 3 + C n − k 3 ) n+6*(C_k^2+C_{n-k}^2+C_k^3+C_{n-k}^3) n+6∗(Ck2+Cn−k2+Ck3+Cn−k3),所以问题就变成怎么把节点分开了,一开始就这个问题想了很多假算法,并查集用了一半发现不对,最后发现不就dfs就好了
代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
typedef long long ll;
int n,u,v,w;
struct Edge{
int v,w,next;
}edge[N*2];
int cnt,head[N];
int k;
ll c[N][5];
void init(){
cnt=0;
k=0;
memset(head,-1,sizeof(head));
c[1][1]=1;
for(int i=1;i<=10005;i++){
c[i][0]=1;
for(int j=1;j<=3 && j<=i;j++){
if(i==1 && j==1){
continue;
}
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}
}
void addEdge(int u,int v,int w){
edge[cnt]=Edge{
v,w,head[u]};
head[u]=cnt++;
edge[cnt]=Edge{
u,w,head[v]};
head[v]=cnt++;
}
void dfs(int d,int u,int p){
if(d%2==0){
//printf("%d %d\n",u,d);
k++;
}
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].v;
int w=edge[i].w;
if(v==p){
continue;
}
dfs(d+w,v,u);
}
}
int main(void){
scanf("%d",&n);
init();
for(int i=0;i<n-1;i++){
scanf("%d%d%d",&u,&v,&w);
w%=2;
addEdge(u,v,w);
}
dfs(0,1,-1);
//printf("%d\n",k);
ll ans=n;
if(k>=2){
ans+=6ll*c[k][2];
}
if(n-k>=2){
ans+=6ll*c[n-k][2];
}
if(k>=3){
ans+=6ll*c[k][3];
}
if(n-k>=3){
ans+=6ll*c[n-k][3];
}
printf("%lld\n",ans);
return 0;
}