P2986 [USACO10MAR] Great Cow Gathering G（换根dp）

思路:这题有一个树形dp中比较明显的特征.
1.无根树2.似乎父子关系并不是那么显然
考虑换根dp,虽然我们并不知道哪个点最优,但我们仍然能求解出以一个点为集合点的时候,其他点到这个集合点时的答案
然后,我们考虑利用求出来的这个点,维护父子关系,从而求出一个表$dp2(u)$以$u$为集合点时的答案.
不妨设$1$为根,先求出其他点到1的答案是多少.以及1为根时的子树大小,对应的路径贡献$dp1(u)$
接下来考虑换根dp。假设我们知道了以$u$为集合点时,其他点到它的路径和$dp2(u)$.对于$u$的儿子$v$,有以下关系
$dp2(v)=dp2(u)-(sz[v]\ast w)+(sum-sz[v])\ast w$
$(sum-sz[v])\ast w$代表了,父亲除了$v$这个子树以外的所有点通过当前边走到了$v$这个点,一共有$(sum-sz[v])$个牛,边权为$w$.但由于$v$不用再走向父亲了,故扣去$sz[v]\ast w$的贡献。
总结:这是一类奇葩的树形dp。怎么说,就是让你求出一个点的解之后,根据解和解之间的父子关系（主要是兄弟的信息合并到父亲身上了）,然后更新儿子的一类dp。常常求出根的dp,再用根的dp值更新儿子

/*
Stairs upon the temple
I climb and I crawl in
People travel millions of miles just to see it
But they never conquer this way
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<pii> G[maxn];
ll dp1[maxn];ll sz[maxn];int a[maxn];
int n;ll sum=0;
void dfs1(int u,int fa){
	sz[u] = a[u];
	for(auto [v,w] : G[u]){
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		dp1[u] += dp1[v] + sz[v]*w;
	}
}
ll dp2[maxn];
void dfs2(int u,int fa){
	for(auto [v,w] : G[u]){
		if(v==fa) continue;
		dp2[v] = dp2[u]+(sum-2*sz[v])*w;
		dfs2(v,u); 
	}
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
	for(int i=1;i<=n-1;i++){
		int u,v,w;cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	dfs1(1,0);
	dp2[1] = dp1[1];
	dfs2(1,0);
	ll ans = 1e15+7;
	for(int i=1;i<=n;i++){
		ans = min(ans,dp2[i]);
	}
	cout<<ans<<"\n";
}
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