自动搬运

查看原文

来自洛谷，原作者为

	yyyyxh OI 是啥 (O_o)？

搬运于2025-08-24 22:31:03，当前版本为作者最后更新于2022-01-25 16:42:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考虑 $i$ 向 $a_i$ 连边，构成一个内向基环树，注意到环上的人的 Rating 都应相等，而树上祖先的 Rating 都比后代小。

假设只有一棵树的情况。注意到这样一个事实：

当确定好不更改哪一些人的 Rating 时，如果这些人的 Rating 满足了他们之间已经有了的限制关系，剩下的人通过更改 Rating 一定能够满足题意。

问题转化成了保留一定数量的点满足限制关系，且这些点的权值和最大，想到树形 DP。

设 $f_u$ 表示第 $u$ 个人必须选，其子树中的选择的点权值和的最大值。

$$f_u=c_u+\max_{S\in subtree(u)/\{u\}}\sum_{v \in S} f_v $$

其中 $S$ 是两两没有祖先关系且 Rating 都大于 $h_u$ 的一些点的集合。

发现这些点的选取跟 $h_u$ 有关，把 $h_u$ 离散化后记这些转移式右边那坨为 $g_{u,i}$，表示仅考虑那些 $h_v\geq i$ 的点的答案。

这样子就 $f_u=c_u+g_{u,h_u}$ 了。

转移 $g$ 数组就把各个儿子对应位置的值相加，再与父亲的 DP 值 $[1,h_u]$ 前缀取 max 即可，线段树合并维护。

现在线段树要支持区间取 max 和合并，也就是说要取 max 还要加，想了很久。

后来问了同机房数据结构神仙才知道要维护两个懒标记，像线段树2一样先 max 后 +，本质上是广义矩阵乘法，写一个 struct 复合懒标记即可。

至于环上的话枚举将值修改成环上的哪一个值或者是全局最小值，取最大值统计答案。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int _=200003;
int n,cnt;
int a[_],h[_],c[_],t[_];
int read(){
	char c=getchar();int x=0;
	while (c<48||c>57) c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while (c>=48&&c<=57);
	return x;
}
typedef long long ll;
struct tags{ll a,c;tags(ll A=0,ll C=0):a(A),c(C){}};
tags operator*(const tags x,const tags y){
	return tags(max(x.a,y.a-x.c),x.c+y.c); //这里需要稍微推下式子
}
int hd[_],ver[_],nxt[_],tot;
void add(int u,int v){nxt[++tot]=hd[u];hd[u]=tot;ver[tot]=v;}
tags sg[_<<6];
int lc[_<<6],rc[_<<6];
void pushdown(int p){
	if (sg[p].a||sg[p].c){
		if (!lc[p]) lc[p]=++cnt;
		sg[lc[p]]=sg[lc[p]]*sg[p];
		if (!rc[p]) rc[p]=++cnt;
		sg[rc[p]]=sg[rc[p]]*sg[p];
		sg[p]=tags();
	}
}
ll query(int x,int &p,int l=1,int r=n){
	if (!p) p=++cnt;
	if (l==r) return sg[p].a+sg[p].c;
	pushdown(p);
	int mid=(l+r)>>1;
	if (x<=mid) return query(x,lc[p],l,mid);
	else return query(x,rc[p],mid+1,r);
}
void modify(int x,ll v,int &p,int l=1,int r=n){
	if (!p) p=++cnt;
	if (x>=r) {sg[p]=sg[p]*tags(v,0);return;}
	pushdown(p);
	int mid=(l+r)>>1;
	modify(x,v,lc[p],l,mid);
	if (x>mid) modify(x,v,rc[p],mid+1,r);
}
int merge(int u,int v){
	if (!u||!v) return u^v;
	if (!lc[u]&&!rc[u]) u^=v^=u^=v;
	if (!lc[v]&&!rc[v]) sg[u]=sg[u]*tags(0,sg[v].a+sg[v].c);
    //每一次都pushdown强行新建节点复杂度会爆炸，所以没有儿子节点时改为添加加法懒标记
	else pushdown(u),pushdown(v);
	lc[u]=merge(lc[u],lc[v]);
	rc[u]=merge(rc[u],rc[v]);
	return u;
}
int rt[_];ll buc[_];
bool vis[_],cir[_],tmp[_];
void dfs(int u){
	for (int i=hd[u]; i; i=nxt[i]){
		int v=ver[i];
		if (cir[v]) continue;
		dfs(v);
		rt[u]=merge(rt[u],rt[v]);
	}
	ll v=query(h[u],rt[u])+c[u];
	if (!cir[u]) modify(h[u],v,rt[u]);
}
int main(){
	ll sum=0; n=read();
	for (int i=1; i<=n; ++i){
		a[i]=read(); t[i]=h[i]=read();
		sum+=c[i]=read(); add(a[i],i);
	}
	sort(t+1,t+n+1);
	int rk=unique(t+1,t+n+1)-t-1;
	for (int i=1; i<=n; ++i) h[i]=lower_bound(t+1,t+rk+1,h[i])-t;
	for (int i=1; i<=n; ++i)
		if (!vis[i]){
			int cur=i;
			while (!vis[cur]) tmp[cur]=vis[cur]=1,cur=a[cur];
			if (tmp[cur]) while (!cir[cur]) cir[cur]=1,cur=a[cur];
			cur=i;while (tmp[cur]) tmp[cur]=0,cur=a[cur];
		}
	for (int i=1; i<=n; ++i) if (cir[i]) dfs(i);
	for (int i=1; i<=n; ++i)
		if (cir[i]){
			int cur=i;
			while (cir[cur]){
				cir[cur]=0;
				if (cur^i) rt[i]=merge(rt[i],rt[cur]);
				buc[h[cur]]+=c[cur];
				cur=a[cur];
			}
			ll res=query(1,rt[i]);
			while (!tmp[cur]){
				tmp[cur]=1;
				res=max(res,query(h[cur],rt[i])+buc[h[cur]]);
				cur=a[cur];
			}
			sum-=res;
			while (tmp[cur]){
				tmp[cur]=0;
				buc[h[cur]]=0;
				cur=a[cur];
			}
		}
	printf("%lld\n",sum);
	return 0;
}

时间复杂度 $\mathcal{O}(n\log_2n)$