关键词:树形DP 上下DP
相关题目:$CF1060E$

题意

有一颗 $n(n\leq 200000)$ 个点的树,边权均为1

若两个点在树上具有一个相同的相邻点,则在新图上建立一条链接这两点的边
换句话说若$u$和$a$在树上有连边,$v$和$a$也有连边,则在新图上建立边$(u,v)$

求在新图上所有点对之间的最短距离之和

Solution

考虑每个点对*在原树和新图上的距离变化,设原树距离为$Len$

若$Len$为偶数,则在路径上每两点之间都有一条新边,新距离为$\frac{Len}{2}$
若$Len$为奇数,则在路径上多了一个点要使用原树上的边,新距离为$\frac{Len}{2}+1$

因此,若我们可以知道以每个点为起点的到所有点的路径长度和,以及其中长度为奇数的路径的条数就可以统计答案了

考虑如何求这两个东西,想到树形DP
但是普通的树形DP是从叶节点到一个固定的根统计答案的,而这里我们需要知道的是以每个点为根的答案

这时候就需要引入一个叫上下DP的东西

似乎是机房特供?向机房大佬低头!

对每个点记录三个值

  • sum:以该点为起点的所有路径长度和
  • s1: 以该点为起点的长度为奇数的路径条数
  • s2: 以该点为起点的长度为偶数的路径条数

然后我们现在需要从一个点 $u$ 将答案转移掉另一个点 $v$,且它们在原树中有连边
发现所有路径的长度变化都取决于边$(u,v)$是被包含进去了还是不再取了

到$v$点及其子树的点的路径变短了,到其余点的路径变长了,而路径长度的奇偶性则对换了一下

1
2
3
4
sum[v]=sum[u]+size[u]-2*size[v];
size[v]=size[u];
s1[v]=s2[u];
s2[v]=s1[u];

那么事情就好办了
将以每个点为根的答案累加,由于所有路径都被算了两次,最后再除以2就好了

依我个人的理解,上下DP就是在树上将以不同点为根的答案进行转移
在转移过程中只用考虑转移的这条边对答案的影响就好了

代码

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
#include <cstdio>
const int N=210000;
using namespace std;
long long sum[N],ans;
int s1[N],s2[N],size[N],n;
int to[N<<1],nxt[N<<1],head[N],cnt;
inline void add(int u,int v){
to[++cnt]=v,nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs1(int u,int ff){
size[u]=1;
for(int i=head[u];i;i=nxt[i])
if(to[i]!=ff) {
dfs1(to[i],u);
size[u]+=size[to[i]];
}
}
void dfs2(int u,int ff){
s2[u]=1;
for(int i=head[u],v=to[i];i;i=nxt[i],v=to[i]){
if(v==ff) continue;
dfs2(v,u);
sum[u]+=sum[v]+size[v];
s1[u]+=s2[v];
s2[u]+=s1[v];
}
}
void dfs3(int u,int ff){
ans+=sum[u]+s1[u]; //先直接累加原值,到输出时直接/4
for(int i=head[u],v=to[i];i;i=nxt[i],v=to[i]){
if(v==ff) continue;
sum[v]=sum[u]+size[u]-2*size[v];
size[v]=size[u];
s1[v]=s2[u];
s2[v]=s1[u];
dfs3(v,u);
}
}
int main(int argc, char const *argv[]){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y), add(y,x);
}
dfs1(1,0); //处理出子树大小
dfs2(1,0); //用树形DP算出以1为根时的答案
dfs3(1,0); //将答案转移到所有点上
printf("%lld\n",ans/4);
return 0;
}