【每日一题】Treepath

戳我传送

思路：

方法一：因为每条边的权值都是一样，所以可以用LCA求得每个结点想对于根结点1的深度，在这里深度就是距离。从偶数层到偶数层和从奇数层到奇数层的路径都是偶数。这里可以用链式向前星存图，然后dfs统计有多少个奇数层a和偶数层b，不必要区分偶数层和奇数层，答案就是 + 。如果1e5-1个结点都连在根结点1上，这时的答案最大，需要用long long。
复杂度： (log n)。
Code戳我

方法二：设f[i][0/1]表示以i为根的子树中，与根节点i的距离为偶数(0)奇数(1)的点的数量。
转移方程显然是f[u][x]+=f[v][x^1]，f[u][x^1]+=f[v][x]。
答案就包括父结点u子树集合里到u为偶数的点数 * v子树集合里到u为奇数的点数和父结点u子树集合里到u为奇数的点数 * v子树集合里到u为偶数的点数，这些方案都经过子树的根u。一定不能先更新f再求ans，因为两个点匹配一定要在两个不同的集合，在一个集合就会出现重复。
复杂度： (log n)。

Code：

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
int to[200005],Next[200005],head[100005],tot;
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
long long ans;
int f[100005][2];
void dfs(int u,int fa) {
    f[u][0]=1;
    for(int i=head[u];i;i=Next[i]) {
        int y=to[i];
        if(y==fa) continue;
        dfs(y,u);
        ans+=f[u][1]*f[y][0];
        ans+=f[u][0]*f[y][1];
        f[u][0]+=f[y][1];
        f[u][1]+=f[y][0];
    }
}
int main() {
    int n=read();
    for(int i=2;i<=n;++i) {
        int x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    cout<<ans<<endl;
}