题意

给定一棵n个点的树,问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。


题解:

方案1:假设根节点为1,那么树上两点i,j间的距离为 图片说明 由于后面的差一定是偶数,那么对于任意两点只要满足图片说明
为偶数即可。(dep为深度)
所以所有相同奇偶性深度的点都之间的距离都为偶数,那么我们dfs分别统计一下 计算就可以啦~


代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

int n,x,y;
LL a[2];
VI G[maxn];
void dfs(int u,int fa,int d){
     a[d%2]++;
     for(int v:G[u]) if(v!=fa){
        dfs(v,u,d+1);
     }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        G[x].pb(y);G[y].pb(x);
    }
    dfs(1,0,0);
    printf("%lld\n",(a[0]*a[0]-a[0]+a[1]*a[1]-a[1])/2);
}