自动搬运

查看原文

来自洛谷，原作者为

	linruichen 程序漏洞叫特性，设计漏洞叫特色。

搬运于2025-08-24 22:59:31，当前版本为作者最后更新于2025-06-06 22:54:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目大意

给定矿点个数 $n$ 和部下人数 $m$ 与为生成数据 $A$，$B$，$Q$，点的父亲节点同 $n$ 个矿点有几个部下带来的收益。进行 $C$ 次询问，事件 0 为更改第 $p$ 个矿点的收益，事件 1 为求 $u$，$v$ 中 $u$ 子树（包括 $u$）与 $u$ 到 $v$ 的链（$u$ 应排除出选择，否则影响结果）怎样分配收益最大，其中 $u$ 到 $v$ 的链只能安排一次部下（个数不限）。

解题思路

看见选择出最大值可以想到 DP，处理链想到树链剖分，及将树进行树链剖分，再用线段树建树，线段树的每个节点存储一个数组 $\operatorname{f}$，$\operatorname{g}$（都为一维），在线段树中分别表示当前节点的所有叶子节点分配 $i$ 个部下带来的最高收益（用 $O(m^2)$ 的时间进行合并），当前节点的一个叶子节点分配 $i$ 个部下带来的最高收益（用 $O(m)$ 的时间进行合并）。子树内的答案只需区间查询（查询 $\operatorname{f}$），链上的只需树链剖分即可（查询 $\operatorname{g}$），时间复杂度分别为 $O(m^2 \log n)$，$O(m \log^2 n)$，修改则直接更改后合并，时间复杂度为 $O(m^2 \log n)$，总时间复杂度为 $O(C(m^2 \log n + m \log^2 n))$，可行。

参考代码

#include<bits/stdc++.h>
using namespace std;
long long tou[20010],zui[20010],wei[20010],bian[20010],shen[20010],da[20010],
    son[20010],t,b[20010],fa[20010],n,m,B,A,Q,X,Y,p,c[51],d[51];
struct w{
	long long x,y;
}a[100010];
struct o{
	long long a[51],g[51];
}f[80010],uv[20010];
inline long long Getint()
{
    A=((A^B)+B/X+B*X)&Y;
    B=((A^B)+A/X+A*X)&Y;
    return (A^B)%Q;
}
void ww(long long die,long long ye)
{
	fa[die]=ye;
	da[die]=1;
	for(long long i=b[die];i;i=a[i].y)
	if(a[i].x!=ye)
	{
		shen[a[i].x]=shen[die]+1;
		ww(a[i].x,die);
		da[die]+=da[a[i].x];
	}
	for(long long i=b[die];i;i=a[i].y)
	if(a[i].x!=ye)
		if(da[son[die]]<da[a[i].x])
			son[die]=a[i].x;
}
void www(long long die,long long ye)
{
	if(son[die])
	{
		
		tou[son[die]]=tou[die];
		wei[son[die]]=++t;
		bian[wei[son[die]]]=son[die];
		zui[son[die]]=wei[son[die]];
		www(son[die],die);
		zui[die]=max(zui[die],zui[son[die]]);
	}
	for(long long i=b[die];i;i=a[i].y)
		if(a[i].x!=ye&&a[i].x!=son[die])
		{
			tou[a[i].x]=a[i].x;
			wei[a[i].x]=++t;
			zui[a[i].x]=wei[a[i].x];
			bian[wei[a[i].x]]=a[i].x;
			www(a[i].x,die);
			zui[die]=max(zui[die],zui[a[i].x]);
		}
}
void jian(long long k,long long l,long long r)
{
	if(l==r)
	{
		for(long long i=0;i<=m;i++)
			f[k].a[i]=uv[bian[l]].a[i],
			f[k].g[i]=uv[bian[l]].a[i];
		return;
	}
	long long mid=(l+r)/2;
	jian(k*2,l,mid);
	jian(k*2+1,mid+1,r);
	for(long long i=0;i<=m;i++)
		for(long long j=0;j<=i;j++)
			f[k].a[i]=max(f[k].a[i],f[k*2].a[j]+f[k*2+1].a[i-j]);
	for(long long i=0;i<=m;i++)
		f[k].g[i]=max(f[k*2].g[i],f[k*2+1].g[i]);
}
void gai(long long k,long long l,long long r,long long x)
{
	if(l==r)
	{
		for(long long i=0;i<=m;i++)
			f[k].a[i]=uv[bian[l]].a[i],
			f[k].g[i]=uv[bian[l]].a[i];
		return;
	}
	long long mid=(l+r)/2;
	if(x<=mid)gai(k*2,l,mid,x);
	if(x>mid)gai(k*2+1,mid+1,r,x);
	for(int i=0;i<=m;i++)
		f[k].g[i]=f[k].a[i]=0;
	for(long long i=0;i<=m;i++)
		for(long long j=0;j<=i;j++)
			f[k].a[i]=max(f[k].a[i],f[k*2].a[j]+f[k*2+1].a[i-j]);
	for(long long i=0;i<=m;i++)
		f[k].g[i]=max(f[k*2].g[i],f[k*2+1].g[i]);
}
void qui_f(long long k,long long l,long long r,long long x,long long y)
{
	if(x<=l&&r<=y)
	{
		for(long long i=m;i>=0;i--)
		for(long long j=i;j>=0;j--)
			c[i]=max(c[i],c[j]+f[k].a[i-j]);
		return;
	}
	long long mid=(l+r)/2;
	if(x<=mid)qui_f(k*2,l,mid,x,y);
	if(y>mid)qui_f(k*2+1,mid+1,r,x,y);
}
void qui_g(long long k,long long l,long long r,long long x,long long y)
{
	if(x<=l&&r<=y)
	{
		for(long long i=0;i<=m;i++)
			d[i]=max(d[i],f[k].g[i]);
		return;
	}
	long long mid=(l+r)/2;
	if(x<=mid)qui_g(k*2,l,mid,x,y);
	if(y>mid)qui_g(k*2+1,mid+1,r,x,y);
}
void llca(long long x,long long y)
{
	long long fx=tou[x],fy=tou[y];
	while(fx!=fy)
	{
		if(shen[fx]<shen[fy])
			swap(fx,fy),swap(x,y);
		qui_g(1,1,n,wei[fx],wei[x]);
		x=fa[fx];
		fx=tou[x];
	}
	if(shen[x]>shen[y])
		swap(x,y);
	qui_g(1,1,n,wei[x],wei[y]);
}
main()
{
	scanf("%lld%lld%lld%lld%lld",&n,&m,&A,&B,&Q);
	X=pow(2,16);
	Y=pow(2,31)-1;
	for(long long i=2;i<=n;i++)
	{
		long long x;
		scanf("%lld",&x);
		a[++t].x=x;
		a[t].y=b[i];
		b[i]=t;
		a[++t].x=i;
		a[t].y=b[x];
		b[x]=t;
	}
	ww(1,1);
	t=0;
	tou[1]=1;
	wei[1]=++t;
	bian[wei[1]]=1;
	zui[1]=1;
	www(1,1);
	for(long long i=1;i<=n;i++)
	{
		uv[i].a[0]=0;
		for(long long j=1;j<=m;j++)
			uv[i].a[j]=Getint();
		sort(uv[i].a+1,uv[i].a+m+1);
	}
	jian(1,1,n);
	scanf("%lld",&p);
	while(p--)
	{
		long long z;
		scanf("%lld",&z);
		if(z==0)
		{
			long long x;
			scanf("%lld",&x);
			uv[x].a[0]=0;
			for(long long j=1;j<=m;j++)
				uv[x].a[j]=Getint();
			sort(uv[x].a+1,uv[x].a+m+1);
			gai(1,1,n,wei[x]);
		}
		else
		{
			for(long long i=0;i<=m;i++)
				c[i]=d[i]=0;
			long long u,v,uu;
			scanf("%lld%lld",&u,&v);
			uu=fa[u];
			if(shen[uu]>=shen[v])
				llca(uu,v);
			qui_f(1,1,n,wei[u],zui[u]);
			long long s=0;
			for(long long i=0;i<=m;i++)
				s=max(s,c[i]+d[m-i]);
			printf("%lld\n",s);
		}
	}
}