题意:找到树中距离为偶数的长度的段
题解:偶数的长度,即到根节点距离为奇数的两两组合,到根节点为偶数的两两组合,所以搜索全树
组合方式
时间复杂度:
这个好像是个搜索题.
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; const int maxm=511111; const int maxn=111111; struct EdgeNode { int to; int w; int next; }; struct Node { int x,step; }; EdgeNode edges[maxm]; int N,M; int head[maxn],edge; bool vis[maxn]; int dep[maxn];//第i层的点的个数 queue <Node> que; int maxstep=0; void addedge(int u,int v,int c) { edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++; } void init() { memset(head,-1,sizeof(head)); edge=0; } void BFS() { while(!que.empty()) que.pop(); que.push(Node{1,1}); vis[1]=1; dep[1]++; while(!que.empty()) { Node u=que.front(); que.pop(); for(int i=head[u.x];i!=-1;i=edges[i].next) { int v=edges[i].to; if(vis[v]==0) { vis[v]=1; dep[u.step+1]++; que.push(Node{v,u.step+1}); maxstep=u.step+1; } } } } int main() { int n; init(); scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y,1); addedge(y,x,1); } BFS(); LL odd=0,even=0; for(int i=1;i<=maxstep;i++) { if(i%2==0) odd+=dep[i]; else even+=dep[i]; } LL ans=odd*(odd-1)/2+even*(even-1)/2; printf("%lld\n",ans); return 0; }