【每日一题0415】树上dfs+技巧
技巧：偶 = 偶 + 偶 = 奇 + 奇。
偶数层到偶数层的节点路径长度为偶数，奇数层到奇数层的节点路径长度为偶数，
算出每个节点的深度，统计深度为奇、偶数的节点个数odd、even。
答案就是
树上dfs直接统计深度就可以了
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
ll n,tot,rt,dis[N],fa[N],h[N],ne[N<<1],p[N<<1],wi[N<<1];
void addEdge(int u,int v,int w){p[++tot]=v;ne[tot]=h[u];h[u]=tot;wi[tot]=w;}
void add(int u,int v){p[++tot]=v;ne[tot]=h[u];h[u]=tot;}
ll odd,even;
void dfs(int u,int fa,int dep){
if(dep&1) odd++;
else even++;
for(int i=h[u];i;i=ne[i])if(p[i]!=fa){
dfs(p[i],u,dep+1);
}
}
int main(){
int n;cin>>n;
for(int i=1;i<n;i++){
int x,y;cin>>x>>y;
add(x,y);add(y,x);
}
dfs(1,0,0);
cout<<odd*(odd-1)/2+even*(even-1)/2;
return 0;
} 
查看30道真题和解析