题解 CF1060E 【Sergey and Subway】
eee_hoho
2020-11-19 09:38:40
说个和别的题解不一样的换根dp方法。
首先分析题目发现可以把长度为$2$的路径走成$1$步，所以我们考虑设$f_{u,0/1}$表示以$u$为根的子树，$u$到所有距离自己为偶数$/$奇数的儿子的答案和，$size_{u,0/1}$表示以$u$为根的子树，距离$u$为偶数$/$奇数的儿子个数，于是有转移方程：
$$\begin{cases}f_{u,0}=\sum_{v\in son(u)}f_{v,1}\\f_{u,1}=\sum_{v\in son(u)}f_{v,0}+size_{v,0}\\size_{u,0}=1+\sum_{v\in son(u)}size_{v,1}\\size_{u,1}=\sum_{v\in son(u)}size_{v,0}\end{cases}$$
具体来说就是从儿子和自己奇偶性相反的转移过来。
如果儿子是偶数，那么从$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**
``` cpp
#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;
}
```