Problem Link

题目大意

给定 $n$ 个点的树，每个点有点权 $w_i$，$q$ 次询问 $L,R$，构造一组 $c_i$ 使得每个子树内 $c_i$ 的和都在 $[0,1]$ 之间，最小化 $\sum|c_i|w_i$。

数据范围；$n\le 2\times 10^5,q\le 10^5$。

思路分析

先从 $w_i=1$ 的情况开始分析，此时在哪里填 $c$ 没有区别，只关心总和。

自下而上地开始填 $c_i$，首先在每个叶子上都有 $c_i=L$，在此之后，每个点的子树和都 $\ge L$，我们只要给一些非叶子结点的 $c$ 设为负数以保证其总和 $\le R$，容易证明减到 $<L$ 是不优的。

观察根节点处的变化量，设原有 $k$ 个叶子，那么要让根节点合法，整棵树的变化量至少为 $\max(0,kL-R)$。

不难证明这个界是可以取到的，可以每个 $>R$ 的节点处减到 $R$，可以证明这样不会有冗余操作。

然后考虑 $w_i\in\{0,1\}$ 的情况，容易发现此时我们能在 $w_i=0$ 的点上任意操作，因此我们一定能在每个 $w_i=0$ 的点上把子树和调整到 $L$。

这相当于把每个 $w_i=0$ 的点看成叶子，然后对每个连通块分别求解答案再求和。

设有 $k$ 个叶子的连通块有 $f_k$ 个，答案就是 $\sum_k f_k\times \max(0,kL-R)$，求出第一个 $kL>R$ 的位置维护 $f_k$ 和 $k\times f_k$ 的后缀和即可快速计算答案。

然后考虑一般的情况，由于我们已经会解决 $w_i\in\{0,1\}$ 的情况了，因此不妨猜测更一般的情况可以向这种情况规约。

对每个 $x$，将 $w_i>x$ 的点看成 $1$，$w_i\le x$ 的点看成 $0$，然后对每个 $x$ 求出答案再相加，可以根据本题的直接贪心过程证明之。

依然考虑维护 $\sum f_k$，设 $w_1\sim w_n$ 是递增的，那么我们就要依次删除 $1\sim n$，删除 $1\sim i$ 后的一个叶子数为 $k$ 的连通块对 $f_k$ 的贡献就是 $w_{i+1}-w_i$。

首先我们肯定转成倒序插入节点，可以用并查集维护产生和删除的每个连通块。

并且可以考虑差分，即一个连通块在插入 $x$ 时刻生成，就对 $f_k$ 产生 $+w_x$ 贡献，在插入 $y$ 时刻消失，就对 $f_k$ 产生 $-w_y$ 贡献。

那么这样就可以维护出所有 $f_k$ 并计算答案，最终答案记得加上 $L$ 倍叶子权值的和。

时间复杂度 $\mathcal O(n\log n+q)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2e5+5;
vector <int> G[MAXN];
int n,w[MAXN],fa[MAXN],dsu[MAXN],siz[MAXN];
bool vis[MAXN];
ll cnt[MAXN],s1[MAXN],s2[MAXN],clf;
int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
void add(int x,int c,int v) { cnt[siz[x]]-=v,cnt[siz[x]+=c]+=v; }
void merge(int x,int y,int v) { dsu[y]=x,cnt[siz[y]]-=v,add(x,siz[y],v); }
void ins(int x) {
	vis[x]=true;
	if(fa[x]&&vis[fa[x]]) add(find(fa[x]),-1,w[x]);
	for(int y:G[x]) {
		if(!vis[y]) add(x,1,w[x]);
		else merge(x,y,w[x]);
	}
	if(vis[fa[x]]) merge(find(fa[x]),x,w[x]);
}
void init(vector <int> P,vector <int> W) {
	n=W.size(); vector <int> ord;
	for(int i=1;i<=n;++i) w[i]=W[i-1],ord.push_back(i),dsu[i]=i;
	for(int i=2;i<=n;++i) G[fa[i]=P[i-1]+1].push_back(i);
	for(int i=1;i<=n;++i) if(G[i].empty()) G[i].push_back(0),clf+=w[i];
	sort(ord.begin(),ord.end(),[&](int x,int y){ return w[x]>w[y]; });
	for(int u:ord) ins(u);
	for(int i=n;i>=1;--i) s1[i]=s1[i+1]+cnt[i],s2[i]=s2[i+1]+cnt[i]*i;
}
ll query(int L,int R) {
	int x=min(n,R/L)+1;
	return clf*L+s2[x]*L-s1[x]*R;
}