前言:

emmm,学了点分治,第一眼看到这个题的时候,这不就是个点分治吗...然后看了除了点分治的其他解法..emmm好简单啊.然后我把点分治复习了一遍,顺便敲了下其他的解法~

Solution 1:

思维:假如是边权为1的点,相互之间为偶数距离的点对个数的话,必定满足一个条件,就是黑白染色之后颜色相同.我们不妨设根节点为1,进行一次dfs即可.
复杂度:.
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
vector<int>g[N];
ll f[2];
void dfs(int u,int fa,int dep)
{
    f[dep]++;
    for(int v:g[u])
    {
        if(v==fa)    continue;
        dfs(v,u,dep^1);
    }
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int v,u;
        scanf("%d%d",&v,&u);
        g[v].push_back(u);
        g[u].push_back(v);
    }dfs(1,1,1);
    printf("%lld\n",f[0]*(f[0]-1)/2+f[1]*(f[1]-1)/2);
    return 0;
}

Solution 2:

点分治:直接进行点分治,统计下子树的奇偶性状况,然后计数即可.
复杂度:.
代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50,M=2;
vector<int>g[N];
int root,sz[N],f[N],sum;
ll num[M],ans;
bool vis[N];//标记这个点是否被用过. 
void f_root(int u,int fa)
{
    sz[u]=1,f[u]=0;
    for(int v:g[u])
    {
        if(v==fa||vis[v])    continue;
        f_root(v,u);sz[u]+=sz[v];
        f[u]=max(f[u],sz[v]);
    }f[u]=max(f[u],sum-sz[u]);
    if(f[u]<f[root])    root=u;
}

void cnt_node(int u,int fa,int val)
{
    num[val]++;
    for(int v:g[u])
    {
        if(vis[v]||v==fa)    continue;
        cnt_node(v,u,val^1);
    }
}

void cnt_ans(int u,int fa,int val)
{
    ans+=num[val];
    for(int v:g[u])
    {
        if(vis[v]||v==fa)    continue;
        cnt_ans(v,u,val^1);
    }
}

void cal(int u,int val)
{
    for(int v:g[u])
    {
        if(vis[v])    continue;
        cnt_ans(v,u,val^1);
        cnt_node(v,u,val^1);
    }
}

void solve(int u)
{
    num[0]++;cal(u,0);
    vis[u]=true;
    memset(num,0,sizeof num);
    for(int v:g[u])
    {
        if(vis[v])    continue;
        root=0,sum=sz[v];
        f_root(v,u);
        solve(v);
    }
}

int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int v,u;
        scanf("%d%d",&v,&u);
        g[v].push_back(u);
        g[u].push_back(v);
    }f[0]=n,sum=n,root=0;
    f_root(1,0);solve(root);
    printf("%lld\n",ans);
    return 0;
}