【UR #7 C】水题走四方（DP）

水题走四方

题目链接：UR #7 C

题目大意

给你一棵有根树，有两个人一开始都在根节点。
然后每个人每个时刻可以不动或者走到一个儿子，然后两个人可以不花费时间的把一个人传送到另一个人的位置。
然后问你两个人合起来访问所有点的最小时间是多少。

思路

首先思考一下为啥一定可以走完。
不难想象到就是一个人可以固定在根节点，然后让另一个人走就可以。

于是考虑优化这个过程。
发现如果走剩两个儿子，然后其中一个儿子没走的部分构成一条链，那我们可以让两个人分别走一个儿子，然后构成链的儿子走到底再传回另一个人那边。

那两个人要做的事是可以交换的，所以我们固定一个人给另一个人传，分别称为本人和分身。
那本人走的就是一条链，我们考虑根据这条链来 DP。

但是本人的这条链它不是每个点都会停下来，我们就不能直接 $O(n)$ 去 DP。
于是考虑会从那些点转移：
其实会发现如果有多个，肯定是能停就停，这是一个显然的，因为走的都是同一段。
所以我们应该要问的是从哪个点转移。

---

考虑找，其实就是看要不要等，那你看看等的条件。
其实很显然，就是它除了你这个点挂着的儿子的子树，要有一个儿子的最深深度不小于你。
这样最后它在那走，你走到这里，就要等他走完传到你这里。

我们把转移的位置叫做 $f{r}_x$。
所以呢，我们就可以有一个方法找，我们把当前还没有找到的弄出来，可以直接用类似链表存。（因为你找到的肯定是前面的一段）
然后每次你合并一个子树，你就看两个：其它子树会不会因为它有了 $fr$，它会不会从其它子树得到 $fr$。
然后条件就是 $de{p}_y⩽max{n}_x$（$y$ 是你链表枚举的点，$x$ 是判断的点，如果是其它子树就是父亲点，否则是儿子点）

然后考虑怎么合并，两条合一起似乎不太可能，好像不能用链表了。
但是会发现其实一定只会有一条链，因为它这个是找最长的链给贡献，但是最长的至少一个，那如果是最长的一定会全部删完，两边里面肯定至少有一遍有最大的。

所以我们直接把它的下一个接到有的那个即可，没有就不接。
因为每次是准确找 $fr$，找不到就走，所以是 $O(n)$ 的。

---

接下来就是愉快的 DP 了！
首先是跟 $f{r}_x$ 的转移，就直接把 $f{r}_x$ 的子树中不是 $x$ 这个的子树的加上。
（维护子树大小，每个点的深度，子树深度和即可）

然后其实不难想象会出现没有 $fr$ 的情况，比如只有一个儿子。（注意是父亲只有它这个儿子）
那我们考虑只能从父亲那里过来，所以也可能是 $f_{f{a}_i}+1$。（当然一定要没有 $fr$ 才行）

然后对于叶子节点我们更新一下答案，就可以啦！

代码

#include
#include
#define ll long long

using namespace std;

const int N = 5e6 + 100;
int n, m, fa[N], deg[N], du[N], fr[N];
int sz[N], maxn[N], nxt[N];
char s[N * 2];
ll f[N], sum[N];

int main() {
	scanf("%d", &m);
	scanf("%s", s + 1); int lst = 0;
	for (int i = 1; i <= 2 * m; i++) {
		if (s[i] == '(') {
			n++; fa[n] = lst; lst = n;
		}
		else {
			lst = fa[lst];
		}
	}
	
	for (int i = 2; i <= n; i++) {
		deg[i] = deg[fa[i]] + 1; du[fa[i]]++;
	}
	
	for (int i = n; i > 1; i--) {
		if (!du[i]) {
			sz[i] = 1; sum[i] = deg[i]; maxn[i] = deg[i];
		}
		int x, y;
		for (x = i; x && deg[x] <= maxn[fa[i]]; x = nxt[x]) fr[x] = fa[i];
		for (y = nxt[fa[i]]; y && deg[y] <= maxn[i]; y = nxt[y]) fr[y] = fa[i];
		nxt[fa[i]] = x | y;
		sum[fa[i]] += sum[i]; sz[fa[i]] += sz[i];
		maxn[fa[i]] = max(maxn[fa[i]], maxn[i]);
	}
	
	ll ans = 2e18;
	f[1] = 0; if (!du[1]) ans = min(ans, f[1]);
	for (int i = 2; i <= n; i++) {
		f[i] = 2e18;
		if (fr[i]) f[i] = min(f[i], f[fr[i]] + (sum[fr[i]] - sum[i]) - 1ll * deg[fr[i]] * (sz[fr[i]] - sz[i]));
		if (du[fa[i]] == 1) f[i] = min(f[i], f[fa[i]] + 1);
		if (!du[i]) ans = min(ans, f[i]);
	}
	printf("%lld", ans);
	
	return 0;
}
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