Codeforces1060E 树形dp

Posted on | In , ,

一棵树，在距离为 $2$ 的任意两点之间加一条边，问你加完边之后的任意两点之间的距离总和。
$(n\le 2·10^5)$

题目链接

题解

  • 考虑一个经典的问题：求树上任意两点的距离和，这个直接算每条边的点的数量，算贡献即可。
  • 回到当前这个问题，考虑任意一个点，其他点到这个点的距离和，分开看这个点的子树和父亲节点所在的树
  • 对于子树，这个点的贡献为，分别考虑距离这个点距离为奇数和偶数的数量和奇数长度和以及偶数长度和。
  • 对于父节点的树(除去这个点的所有子树)，可以按照考虑子树相同的dfs顺序，继承父节点的，已经兄弟节点的贡献。

具体细节：
$sz1[u][0/1]$ 分别表示 $u$ 节点的孩子到这个节点距离为偶数和奇数的个数。 $sz2[u][0/1]$ 表示 分别表示 $u$ 节点的父亲到这个节点距离为偶数和奇数的个数。 $dis1[u][0/1]$表示 $u$ 节点的孩纸到这个节点的距离为偶数和奇数的距离总和。
$dis2[u][0/1]$ 表示 $u$ 节点的父亲 到这个节点的距离为偶数和奇数的距离总和。
那么 $ans$ 就是对于当前点， 到当前点的偶数距离/2 + （ 奇数距离+ 奇数个数）/2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5+12;
const int mod=998244353;

int n, sz1[maxn][2], sz2[maxn][2];
ll dis1[maxn][2], dis2[maxn][2];
vector<int>g[maxn];
int u ,v;

void dfs1(int u, int fa)
{
    sz1[u][0]=1;
    for(int i=0;i<int(g[u].size());i++)
    {
        int v=g[u][i];
        if(v==fa) continue;
        dfs1(v, u);
        sz1[u][0]+=sz1[v][1];
        sz1[u][1]+=sz1[v][0];
        dis1[u][0]+=dis1[v][1]+sz1[v][1];
        dis1[u][1]+=dis1[v][0]+sz1[v][0];
    }
}

void dfs2(int u,int fa)
{
    for(int i=0;i<int(g[u].size());i++)
    {
        int v=g[u][i];
        if(v==fa) continue;

        sz2[v][0]+=sz2[u][1];
        sz2[v][0]+=(sz1[u][1]-sz1[v][0]);
        dis2[v][0]+=(dis2[u][1]+sz2[u][1]);
        dis2[v][0]+=(dis1[u][1]-(dis1[v][0]+sz1[v][0])+(sz1[u][1]-sz1[v][0]));

        sz2[v][1]+=sz2[u][0];
        sz2[v][1]+=(sz1[u][0]-sz1[v][1]);
        dis2[v][1]+=(dis2[u][0]+sz2[u][0]);
        dis2[v][1]+=(dis1[u][0]-(dis1[v][1]+sz1[v][1])+(sz1[u][0]-sz1[v][1]));


        dfs2(v, u);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum += dis1[i][0]/2 + (dis1[i][1]+sz1[i][1])/2;
        sum += dis2[i][0]/2 + (dis2[i][1]+sz2[i][1])/2;
    }
    sum/=2;
    printf("%lld\n", sum);
}