APP
本文中用 (T_u) 表示以 (u) 为根的子树。
首先考虑暴力 DP，设 (dp_u) 为当前询问的 (x) 下，节点 (u) 的答案，那么根据题意列出转移方程：
其中那个 (max{dp_v,0}) 就是要不要连到 (v) 的子树里面去，这个最大值并不好处理。
我们把所有对 (dp_u) 有贡献（也就是 (ge 0)）的 (dp_v) 用一条有向边连出来，就得到了从原树拎出来的一片森林，这片森林有一个很好的性质，就是不需要取 (max)，直接用 (dp_v) 转移就行了。
我们把 (dp_u) 展开出来：
发现就是在给每个节点权值加上 (x) 之后，子树的权值和。我们设子树的大小为 (siz_u)，原来子树的权值和为 (val_u)，用加法结合律变一下形就知道 (dp_u=siz_u imes x+val_u)。
到这里，如果我们知道每一时刻的森林形态，我们就解决了这个问题。于是问题就变为了如何获得森林形态。
又要加边又要删边是复杂的，我们注意到当 (x) 单调递增时，(dp_u) 总是单调递增的，(max{dp_v,0}) 的取值会是先取 (0)，然后当 (x) 大到一定程度后变为取 (dp_v)，也就是只加边，且每一条边只加一次。因此将询问离线，按 (x) 升序排序。
我们记录 (nd_u) 表示 (xge nd_u) 时，(u) 与 (fa_u) 之间的边被加上。考虑上面 (dp) 的推导过程，满足 (siz_u imes x+val_uge 0)，变形得 (xge -dfrac{val_u}{siz_u})，(nd_u) 是最小的符合条件的 (x)，即 (nd_u=-dfrac{val_u}{siz_u})。没有被卡常所以我直接用浮点数存了，并没有像其他题解一样上取整。
我们用一个堆来维护二元组 ((u,nd_u))，每次询问时取出 (nd_ule x) 的若干个二元组，把 (u) 和 (fa_u) 之间的边加上即可。
考虑加边对 (siz) 和 (val) 的影响，是 (fa_u) 到所在连通块的根节点路径上节点的 (siz,val) 分别增加 (siz_u,val_u)。于是我们需要用并查集来维护加边后连通块的根，然后用支持链修改、单点查的数据结构维护 (siz,val)，我用的差分套 dfs 序树状数组。
需要注意一条边不能被重复加多次，要特判一下，还有树状数组中对下标 (0) 的处理。
时间复杂度是 (mathcal{O}(nlog n))（(n,m) 同阶）。
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=y;x<=z;x++)
#define per(x,y,z) for(ll x=y;x>=z;x--)
#define debug printf("Running %s on line %d...
",__FUNCTION__,__LINE__)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e6+5;
const double eps = 1e-6;
ll n, m, fa[N], sz[N], a[N], dfn[N], tms, trans[N], ans[N];
vector<ll> e[N];
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
struct Query {
ll u, x, id;
}q[N];
struct Dsu {
ll fa[N];
void init(ll x) {rep(i, 1, x) fa[i] = i;}
ll find(ll x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool merge(ll x, ll y) {
ll u = find(x), v = find(y);
// printf("MERGE %lld(%lld) %lld(%lld)
", x, u, y, v);
if(u == v) return 0;
fa[u] = v;
return 1;
}
}dsu;
struct BIT {
ll c[N];
ll lowbit(ll x) {return x & (-x);}
void add(ll x, ll k) {if(!x) return; for(;x<=n;x+=lowbit(x)) c[x] += k;}
ll Ask(ll x) {if(!x) return 0; ll k = 0; for(;x;x-=lowbit(x)) k += c[x]; return k;}
ll ask(ll l, ll r) {return Ask(r) - Ask(l-1);}
}siz, val;
void addChain(BIT& bit, ll l, ll r, ll x) {
bit.add(dfn[l], x);
bit.add(dfn[fa[r]], -x);
}
ll askVertex(BIT& bit, ll u) {
return bit.ask(dfn[u], dfn[u]+sz[u]-1);
}
struct Need {
ll u;
double nd;
Need(ll a=0, double b=0.0) : u(a), nd(b) {}
~Need() {}
friend bool operator < (const Need& a, const Need& b) {return a.nd > b.nd;}
};
priority_queue<Need> heap;
void dfs(ll u) {
dfn[u] = ++tms;
sz[u] = 1;
for(ll v : e[u]) {
dfs(v);
sz[u] += sz[v];
}
}
tuple<ll, double> check(ll u, ll x) {
ll Siz = askVertex(siz, u);
ll Val = askVertex(val, u);
if(Siz * x + Val >= 0) return make_tuple(1, 0.0);
return make_tuple(0, -1.0 * Val / Siz);
}
void link(ll u, ll x) {
// printf("LINK %lld %lld
", u, x);
for(ll v=0;u!=1;u=v) {
trans[u] = 1;
dsu.merge(u, v=dsu.find(fa[u]));
// printf(" -> %lld %lld
", u, v);
ll Siz = askVertex(siz, u);
ll Val = askVertex(val, u);
addChain(siz, fa[u], v, Siz);
addChain(val, fa[u], v, Val);
auto qwq = check(v, x);
ll ok = get<0>(qwq);
double diff = get<1>(qwq);
if(!ok) {
heap.push(Need(v, diff));
break;
}
}
}
int main() {
scanf("%lld%lld", &n, &m);
rep(i, 2, n) scanf("%lld", &fa[i]);
rep(i, 2, n) e[fa[i]].push_back(i);
rep(i, 1, n) scanf("%lld", &a[i]);
rep(i, 1, m) scanf("%lld%lld", &q[i].u, &q[i].x);
rep(i, 1, m) q[i].id = i;
sort(q+1, q+1+m, [](const Query& a, const Query& b) {
return a.x < b.x;
});
dfs(1);
dsu.init(n);
// puts("!");
rep(i, 1, n) {
// printf("*%lld
", i);
heap.push(Need(i, -1.0*a[i]));
addChain(siz, i, i, 1);
addChain(val, i, i, a[i]);
}
// puts("?");
rep(i, 1, m) {
ll u = q[i].u, x = q[i].x, id = q[i].id;
while(!heap.empty() && heap.top().nd <= 1.0 * x) {
ll v = heap.top().u; heap.pop();
if(!trans[v]) link(v, x);
}
ans[id] = askVertex(siz, u) * x + askVertex(val, u);
}
rep(i, 1, m) printf("%lld
", ans[i]);
return 0;
}
本文摘自 ：https://www.cnblogs.com/
