CF1060E Sergey and Subway

给出一颗(N)个节点的树,现在我们在原图中每个不直接连边但是中间只间隔一个点的两个点之间连一条边.

比如在原图中(u)与(v)连边,(v)与(w)连边,但是(u)与(w)不连边,这时候我们就需要连一条(u)与(w)的边.

现在我们需要求出新图中每一个点对((i,j) (1 leq i leq j leq N))的经过的边数和.

说个和别的题解不一样的换根dp方法。

首先分析题目发现可以把长度为(2)的路径走成(1)步，所以我们考虑设(f_{u,0/1})表示以(u)为根的子树，(u)到所有距离自己为偶数(/)奇数的儿子的答案和，(size_{u,0/1})表示以(u)为根的子树，距离(u)为偶数(/)奇数的儿子个数，于是有转移方程：

具体来说就是从儿子和自己奇偶性相反的转移过来。

如果儿子是偶数，那么从(u)走到儿子需要多走一步；而如果儿子是奇数，那么儿子一定是走了一个长度为(1)的边，所以我们直接走长度为(2)的边，不会产生多的步数。

(size_u,0)里的(+1)是要算上自己。

然后我们再通过一遍换根可以算出来(g_{u,0/1})表示以(u)为根的树，(u)到所有距离自己为偶数(/)奇数的儿子的答案和。

然后(ans)显然就是(frac{sum_{i=1}^ng_{i,1}+g_{i,0}}{2})。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 2e5;
using namespace std;
int n,edge[N * 2 + 5],nxt[N * 2 + 5],head[N + 5],edge_cnt,size[N + 5][2],dep[N + 5],ss[N + 5][2];
long long f[N + 5][2],ans,g[N + 5][2];
void add_edge(int u,int v)
{
    edge[++edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}
void dfs1(int u,int fa)
{
    size[u][0] = 1;
    dep[u] = dep[fa] + 1;
    for (int i = head[u];i;i = nxt[i])
    {
        int v = edge[i];
        if (v == fa)
            continue;
        dfs1(v,u);
        f[u][0] += f[v][1];
        f[u][1] += f[v][0] + size[v][0];
        size[u][0] += size[v][1];
        size[u][1] += size[v][0];
    }
}
void dfs2(int u,int fa)
{
    g[u][0] = f[u][0];
    g[u][1] = f[u][1];
    ss[u][1] = size[u][1];
    ss[u][0] = size[u][0];
    if (fa)
    {
        g[u][0] += g[fa][1] - (f[u][0] + size[u][0]);
        g[u][1] += g[fa][0] - (f[u][1]) + ss[fa][0] - size[u][1];
        ss[u][0] += ss[fa][1] - size[u][0];
        ss[u][1] += ss[fa][0] - size[u][1];
    }
    ans += g[u][0] + g[u][1];
    for (int i = head[u];i;i = nxt[i])
    {
        int v = edge[i];
        if (v == fa)
            continue;
        dfs2(v,u);
    }
}
int main()
{
    scanf("%d",&n);
    int u,v;
    for (int i = 1;i < n;i++)
    {
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        add_edge(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);
    cout<<ans / 2<<endl;
    return 0;
}