Treepath

题意:找到树中距离为偶数的长度的段
题解:偶数的长度,即到根节点距离为奇数的两两组合,到根节点为偶数的两两组合,所以搜索全树
组合方式
时间复杂度:
这个好像是个搜索题.

#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;
}