当前位置：首页 > article >正文

CF1060E Sergey and Subway

article 2024/9/25 11:15:42

树上计数dp，考虑每条边的贡献，树上两点距离用深度与LCA表示

长度为2的两点间可以连一条边，所以对于任意两点 $i, j$ ， $dis2_{i,j}=\lceil dis_{i,j}/2 \rceil=(dis_{i,j}+ (dis_{i,j}\%2==1) )/2$
对于前半部分，我们要求原图上所有点对的距离，通过树形dp计算每条边对两端点集的贡献即可
对于后半部分，我们只需另外统计一下在原图中两点距离为奇数的点即可，对于任意两点： $dis_{i,j}=dep_i+dep_j-2*LCA_{i,j}$ 显然式子中的2*LCA不对奇偶产生影响，所以只需要处理出各点深度即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    vector<vector<int>> e(n+1);
    for (int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    vector<int> dep(n+1);
    vector<ll> sz(n+1);
    ll ans=0,cnt=0;
    function<void(int,int)> dfs=[&](int u,int fa){
        sz[u]=1;
        for (auto v:e[u]){
            if (v==fa) continue;
            dep[v]=dep[u]+1;
            dfs(v,u);
            sz[u]+=sz[v];
        }
        cnt+=(dep[u]%2==1);
        ans+=sz[u]*(n-sz[u]);
    };

    dep[1]=1;
    dfs(1,-1);
    cout<<(ans+cnt*(n-cnt))/2;
    return 0;
}