當(dāng)前位置:首頁(yè) > IT技術(shù) > 其他 > 正文

題解洛谷 P7897【[Ynoi2006] spxmcq】
2022-04-25 23:03:14

本文中用 (T_u) 表示以 (u) 為根的子樹(shù)。

首先考慮暴力 DP,設(shè) (dp_u) 為當(dāng)前詢(xún)問(wèn)的 (x) 下,節(jié)點(diǎn) (u) 的答案,那么根據(jù)題意列出轉(zhuǎn)移方程:

[dp_u=(a_u+x)+sumlimits_{v extrm{ is son of }u}max{dp_v,0} ]

其中那個(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):

[egin{aligned} dp_u&=(a_u+x)+sumlimits_{v extrm{ is son of }u}dp_v\ &=(a_u+x)+sumlimits_{v extrm{ is son of }u}(a_v+x)+sumlimits_{w extrm{ is son of }v}dp_w\ &=vdots\ &=sumlimits_{vin T_u}(a_v+x) end{aligned} ]

發(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),也就是只加邊,且每一條邊只加一次。因此將詢(xún)問(wèn)離線,按 (x) 升序排序。

我們記錄 (nd_u) 表示 (xge nd_u) 時(shí),(u)(fa_u) 之間的邊被加上??紤]上面 (dp) 的推導(dǎo)過(guò)程,滿(mǎn)足 (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)),每次詢(xún)問(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/

開(kāi)通會(huì)員,享受整站包年服務(wù)立即開(kāi)通 >