题意
给定一棵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); }