刷题记录:牛客NC24263[USACO 2018 Feb G]Directory Traversal

传送门:牛客

题目描述:

题目较长,此处省略
输入:
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0
输出:
42
1
2
3
4
5
6
7
8
9
10
11
12
13

感觉是一道较难的二次扫描换根dp的题目

主要思路:

1. 首先分析一下我们的题目,我们会发现当前的节点$u$如果往下走到节点$v$的话,那么消耗的数值为$v文件的name+1$,但是从v节点往上走到$u$节点的话消耗的是$../$,也就是$3$点消费.然后题目的要求就是求出一个文件夹节点,使其到任意其他叶子节点的距离和最小(注意此处我们的文件夹节点默认是有文件的)
2. 然后根据树形dp的套路,我们应该不难想到使用f[u]来记录所有$u$的子树中的叶子节点,并且应该有一个显然的转移想法,当前的$u$节点的距离和应该是所有子节点的距离和,也就是${\sum }_{}^{}{f}_v$,并且在这个的基础上还需要加上当前结点往下走一步的贡献(这个贡献与我们的v节点的长度有关,我们可以先进行预处理,存在w[u][v]中).然后就不难得出我们的dp方程了:

$f[u]+=leaf\_size[v]\ast w[u][i]+f[v];$

$leaf\_size存储的是当前v节点的所有叶子节点的个数$

3. 但是显然的,我们现在存储的只是每一个节点的儿字的贡献,但是事实上我们的路径之和还包括我们的父亲对其的贡献.这就需要我们使用$换根dp$的想法了
4. 我们再使用一个数组$g[u]$来存储我们父亲那边的贡献.这个贡献由两部分组成:
   1.一部分是我们当前结点的兄弟结点的贡献
   2.一部分是我们的当前结点的父亲的父亲的那边的贡献

对于第一部分来说,我们考虑一下我们的文件路径的移动方式,对于我们的兄弟结点中的每一个叶子结点,我们都是需要我们的当前的节点往上移动一步,然后再往下移动到各个节点.这一部分的总贡献就是:$3\ast (leaf\_size[u]-leaf\_size[v])+f[u]-f[v]-w[u][v]\ast leaf\_size[v]$,注意这一部分我们还需要减去我们的刚开始由$u$节点往下走到v节点,因为我们的$f[v]$并没有包括这一部分

对于我们的第二部分来说,我们发现需要求出的父亲的父亲的贡献其实在我们的dfs过程中就可以求出来了,为$g[u]$.但是类似的,我们还需要加上我们的当前节点v走到节点u的贡献.也就是$3\ast (leaf\_size[1]-leaf\_size[u])$

对于最终的答案,就是在所有的$f[u]+g[u]-leaf\_size[1]$中取最小值即可,为什么要减一呢,这是因为我们在之前求路径的时候将每一个叶子节点也多加了一个$$符号,所以我们需要在答案过程中减去每一个叶子节点的多余贡献

下面是具体的代码部分:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n;
vector<ll>tree[maxn],w[maxn];
ll g[maxn],f[maxn];//记录儿子叶子节点的总路径/除儿子以外的叶子节点的和
ll node_length[maxn],leaf_size[maxn];
void dfs1(int u) {
	if(tree[u].size()) {
		for(int i=0;i<tree[u].size();i++) {
			int v=tree[u][i];
			dfs1(v);
			leaf_size[u]+=leaf_size[v];
			f[u]+=leaf_size[v]*w[u][i]+f[v];
		}	
	}else {
		leaf_size[u]=1;
	}
	return ;
}
ll ans=ll_maxn;
void dfs2(int u) {
	if(tree[u].size()) {
		for(int i=0;i<tree[u].size();i++) {
			int v=tree[u][i];
			g[v]=3*(leaf_size[1]-leaf_size[u])+g[u]+3*(leaf_size[u]-leaf_size[v])+f[u]-f[v]-leaf_size[v]*w[u][i];
			dfs2(v);
		}
		ans=min(ans,g[u]+f[u]-leaf_size[1]);
	}
	return ;
}
int main() {
	n=read();string s;int num;int v;
	for(int i=1;i<=n;i++) {
		cin>>s;node_length[i]=s.length();
		num=read();
		for(int j=1;j<=num;j++) {
			v=read();
			tree[i].push_back(v);
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=0;j<tree[i].size();j++) {
			int v=tree[i][j];
			w[i].push_back(node_length[v]+1);
		}
	}
	dfs1(1);
	dfs2(1);
	cout<<ans<<endl;
	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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76