Statement:
有一棵 \(n(n \le 3 \times 10^6)\) 个点的树，每个点有点权 \(w_i\)。定义一次操作为选择树上的一条简单路径，并将这条简单路径上的所有点点权减去 \(1\)。
问至少需要多少次操作，使树上所有点的点权恰好变为 \(0\)。
Solution:
对于这样的问题不好入手，则优先考虑转化。
首先将第 \(i\) 个大点拆成 \(w_i\) 个小点，并将这些点都染上颜色 \(i\)，我们称两个相同颜色的点为兄弟点。
考虑最坏的情况，显然是需要 \(\sum_{i=1}^nw_i\) 这么多次操作的，平摊到每个小点的贡献就是 \(1\)，于是我们考虑一种合并操作。即我们可以通过合并一些小点，使他们的对答案仅仅贡献 \(1\) 次，于是可以消掉一些小点的贡献。容易观察到该过程等价于：
-
找到一组小点，且这组小点对应的大点组成一条简单路径。
-
这些小点没有任何一对是兄弟点。
-
每个点至多连两条边。
最后消掉的贡献 \(ans\) 就是多少条边，换句话说，我们要让边数尽量的大，也就是合并的次数尽量大，并遵循上面的规则。
我们考虑递归解决此问题，假设我们已经到了点 \(u\)。还剩下一些点是未被合并的，这里有一个贪心，我们要让这些点尽量都在这个子问题内合并掉，而不是留给他的父亲去合并。感性理解就是，可能父亲没有这么多点去给你合并，而且如果你废弃了一些点，可能会导致答案变劣。
从而不难设计出一个树形 \(\rm DP\)：记 \(f_u\) 是考虑以 \(u\) 为根的子树中，最多的合并次数。我们记 \(a_u\) 是合并完后，\(u\) 还剩下多少个点，\(s_u\) 是 \(u\) 节点最多合并多少次。
显然 \(s_u = \sum_{v \in subtree(u)}{\min(a_u, a_v)}\)，\(f_u = \sum_{v \in subtree(v)}f_v + s_u\)。
code:
qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e6 + 10;
int n, a[N], f[N], ans;
struct edge{
int v, next;
}edges[N << 1];
int head[N], idx;
void add_edge(int u, int v){
edges[++idx] = {v, head[u]};
head[u] = idx;
}
namespace Generate{
int n,seed;
static const int mod=1e9;
int Rand(int x){
seed=(1ll*seed*0x66CCF+19260817ll)%x+1;
seed=(1ll*seed*0x77CCF+20060428ll)%x+1;
seed=(1ll*seed*0x88CCF+12345678ll)%x+1;
seed=(1ll*seed*0x33CCCCFF+10086001ll)%x+1;
return seed;
}
void RS(){ //你需要传入三个参数，分别表示点权，一条边的两个端点
int cnt=0;
for(int i=1;i<=n;i++)a[i]=Rand(mod);
for(int i=2;i<=n;i++){
int fa=Rand(i-1);
cnt++;
add_edge(fa, i); add_edge(i, fa);
}
}
};
void dfs(int u, int fa){
int sum = 0;
for(int i = head[u]; i; i = edges[i].next){
int v = edges[i].v;
if(v == fa) continue;
dfs(v, u); f[u] += f[v]; sum += min(a[u], a[v]);
}
f[u] += min(a[u] * 2, sum); a[u] -= min(a[u], max(0ll, sum - a[u]));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int opt; cin >> opt;
if(opt == 1){
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], ans += a[i];
for(int i = 1; i < n; i++){
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
}
}
else{
cin >> Generate::seed >> n;
Generate::n = n;//记得赋值
Generate::RS(); //开始工作
for(int i = 1; i <= n; i++) ans += a[i];
}
dfs(1, 0);
cout << ans - f[1];
return 0;
}