APP
本文中用 (T_u) 表示以 (u) 為根的子樹(shù)。
首先考慮暴力 DP，設(shè) (dp_u) 為當(dāng)前詢問(wèn)的 (x) 下，節(jié)點(diǎn) (u) 的答案，那么根據(jù)題意列出轉(zhuǎn)移方程：
其中那個(gè) (max{dp_v,0}) 就是要不要連到 (v) 的子樹(shù)里面去，這個(gè)最大值并不好處理。
我們把所有對(duì) (dp_u) 有貢獻(xiàn)（也就是 (ge 0)）的 (dp_v) 用一條有向邊連出來(lái)，就得到了從原樹(shù)拎出來(lái)的一片森林，這片森林有一個(gè)很好的性質(zhì)，就是不需要取 (max)，直接用 (dp_v) 轉(zhuǎn)移就行了。
我們把 (dp_u) 展開(kāi)出來(lái)：
發(fā)現(xiàn)就是在給每個(gè)節(jié)點(diǎn)權(quán)值加上 (x) 之后，子樹(shù)的權(quán)值和。我們?cè)O(shè)子樹(shù)的大小為 (siz_u)，原來(lái)子樹(shù)的權(quán)值和為 (val_u)，用加法結(jié)合律變一下形就知道 (dp_u=siz_u imes x+val_u)。
到這里，如果我們知道每一時(shí)刻的森林形態(tài)，我們就解決了這個(gè)問(wèn)題。于是問(wèn)題就變?yōu)榱巳绾潍@得森林形態(tài)。
又要加邊又要?jiǎng)h邊是復(fù)雜的，我們注意到當(dāng) (x) 單調(diào)遞增時(shí)，(dp_u) 總是單調(diào)遞增的，(max{dp_v,0}) 的取值會(huì)是先取 (0)，然后當(dāng) (x) 大到一定程度后變?yōu)槿?(dp_v)，也就是只加邊，且每一條邊只加一次。因此將詢問(wèn)離線，按 (x) 升序排序。
我們記錄 (nd_u) 表示 (xge nd_u) 時(shí)，(u) 與 (fa_u) 之間的邊被加上?？紤]上面 (dp) 的推導(dǎo)過(guò)程，滿足 (siz_u imes x+val_uge 0)，變形得 (xge -dfrac{val_u}{siz_u})，(nd_u) 是最小的符合條件的 (x)，即 (nd_u=-dfrac{val_u}{siz_u})。沒(méi)有被卡常所以我直接用浮點(diǎn)數(shù)存了，并沒(méi)有像其他題解一樣上取整。
我們用一個(gè)堆來(lái)維護(hù)二元組 ((u,nd_u))，每次詢問(wèn)時(shí)取出 (nd_ule x) 的若干個(gè)二元組，把 (u) 和 (fa_u) 之間的邊加上即可。
考慮加邊對(duì) (siz) 和 (val) 的影響，是 (fa_u) 到所在連通塊的根節(jié)點(diǎn)路徑上節(jié)點(diǎn)的 (siz,val) 分別增加 (siz_u,val_u)。于是我們需要用并查集來(lái)維護(hù)加邊后連通塊的根，然后用支持鏈修改、單點(diǎn)查的數(shù)據(jù)結(jié)構(gòu)維護(hù) (siz,val)，我用的差分套 dfs 序樹(shù)狀數(shù)組。
需要注意一條邊不能被重復(fù)加多次，要特判一下，還有樹(shù)狀數(shù)組中對(duì)下標(biāo) (0) 的處理。
時(shí)間復(fù)雜度是 (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/
