牛客练习赛30——小K的疑惑

读题看懂样例就花了好久…
给一棵树，树上任意两个点的距离表示为距离%2，那这样任意两个点之间距离要不就是0要不就是1了，这样就能把树上的点分成两个集合，相同集合内点相距0，不同集合点相距1，然后推出公式就是$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;
}