自动搬运

查看原文

来自洛谷，原作者为

	kkxacj Full of Hope.

搬运于2025-08-24 23:04:58，当前版本为作者最后更新于2024-12-12 10:25:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言

应发电机要求，感谢发电机发的电和思路。

思路

根据题目描述，我们需要遍历的点是一条从祖先到儿子的链，但如果这样覆盖就不好统计哪些点未遍历，考虑反过来，即以从儿子到祖先的方式来遍历，这样只需要保证以 $i$ 的为根的子树都被遍历时，能往上 $j$ 次的最小代价就行了。

对于输入的 $m$ 种操作，我们将串 $s$ 翻转，然后用 map 存串为 $x$ 时的最小代价和编号，特殊的，我们额外给 $1$ 这个点赋一个特殊符号，然后将这个特殊符号代价赋值为 $-1$，这是因为这种情况不算操作数，方便特判。

注意到 $n \le 500$，我们的只需要时间复杂度在 $n^3$ 以内即可，直接设 $f_{i,j}$ 表示以 $i$ 为根的子树都被覆盖且还可以从 $i$ 开始向上覆盖 $j$ 个数，也就是若 $1 \le j$，则会覆盖从它父亲开始的 $j-1$ 个祖先，我们先考虑 $t=0$ 的情况。

对于合并，我们直接 $n^2$ 合并，设 $v$ 为 $i$ 的儿子，若 $v$ 是第一个遍历到的儿子，则 $g_{i,j} = f_{v,j}$，否则 $g_{i,\max\left(j,z-1\right)} = \min\left(g_{i,\max\left(j,z-1\right)},f_{i,j}+f_{v,z}\right)$，每次合并后 $f_{i,j}=g_{i,j}$。

合并完后，一直跳祖先得到一个字符串，若有这种操作，就尝试更新。

对于判无解情况，我们可以给初值赋为一个很大的数，若最终值大于等于这个很大的数，就说明无解。

给出 $t=0$ 的代码供参考look。

对于 $t=1$，我们可以开 vector 来记录，$v_{i,j}$ 表示在此状态下的操作集合，在合并时，记录一下从哪两个地方转过来的，在最后合并就可以保证复杂度正确，合并完后的操作也同理。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace IO
{
	template<typename T>
	void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
	template<typename T,typename... Args>
	void read(T &_x,Args&...others){Read(_x);Read(others...);}
	const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
	#define pc(x) buf[plen++]=x
	#define flush(); fwrite(buf,1,plen,stdout),plen=0;
	template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 510,M = 1e5+10;
int n,m,t,x,y,cnt,head[N],f[N][N],dep[N],g[N][N],id[N][N],id1[N][N],id2[N][N],id3[N][N],l,r,fa[N],o,o1,o2;
map<string,int>mp,mp1;
vector<pair<int,pair<int,int> > >v[N][N],v1[N][N];//可以写一个struct，但我懒了 
pair<int,pair<int,int> >X;
struct w
{
	int to,nxt;
}b[M<<1];
char c[N];
string s;
inline void add(int x,int y)
{
	b[++cnt].nxt = head[x];
	b[cnt].to = y;
	head[x] = cnt;
}
void dfs(int x,int y)
{
	dep[x] = dep[y]+1;  fa[x] = y;
	for(int i = 0;i <= dep[x];i++) f[x][i] = 1e15;//赋初值 
	for(int i = head[x];i;i = b[i].nxt)
	{
		dfs(b[i].to,x);
		for(int j = 0;j <= dep[x];j++) id[x][j] = id1[x][j] = 0,v1[x][j].clear(),g[x][j] = 1e15;
		if(i == head[x])
		{
			for(int z = 1;z <= dep[b[i].to];z++) id[x][z-1] = b[i].to,id1[x][z-1] = z,g[x][z-1] = min(g[x][z-1],f[b[i].to][z]);
		}
		else
		{
			for(int j = 0;j <= dep[x];j++) 
				for(int z = 1;z <= dep[b[i].to];z++)
					if(f[x][j]+f[b[i].to][z] < g[x][max(j,z-1)])
					{
						g[x][max(j,z-1)] = min(g[x][max(j,z-1)],f[x][j]+f[b[i].to][z]);
						id[x][max(j,z-1)] = b[i].to,id1[x][max(j,z-1)] = z;
						id2[x][max(j,z-1)] = x,id3[x][max(j,z-1)] = j;//记录位置 
					}
		}
		for(int j = 0;j <= dep[x];j++) //最后更新保证复杂度 
		{
			if(id[x][j])
				for(int o = 0;o < v[id[x][j]][id1[x][j]].size();o++) 
					v1[x][j].push_back(v[id[x][j]][id1[x][j]][o]);
			if(id2[x][j])
				for(int o = 0;o < v[id2[x][j]][id3[x][j]].size();o++) 
					v1[x][j].push_back(v[id2[x][j]][id3[x][j]][o]);
		}
		for(int j = 0;j <= dep[x];j++) v[x][j] = v1[x][j],f[x][j] = g[x][j];
	}
	if(head[x] == 0) f[x][0] = 0;
	o = x,o1 = f[x][0],o2 = 0; s = "";
	for(int i = 1;i <= dep[x];i++) 
	{
		s += c[o]; 
		if(mp[s] == -1 && o1 < f[x][i]) v[x][i] = v[x][o2],f[x][i] = min(o1,f[x][i]); //芝士特殊情况，不用加这次操作（因为1不用遍历） 
		if(mp[s] != 0 && mp[s]+o1 < f[x][i]) v[x][i] = v[x][o2],v[x][i].push_back(make_pair(fa[o],make_pair(x,mp1[s]))),f[x][i] = min(o1+mp[s],f[x][i]);//更新，加入一次新的操作 
		if(f[x][i] < o1) o2 = i,o1 = min(f[x][i],o1);
		o = fa[o];
	}
}
signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),read(t); c[1] = '0';
	for(int i = 2;i <= n;i++) read(x),cin>>c[i],add(x,i); 
	mp["0"] = -1;
	for(int i = 1;i <= m;i++)
	{
		read(x),cin>>s; l = 0,r = s.size()-1;
		while(l<r) swap(s[l],s[r]),l++,r--;
		if(!mp[s]) mp[s] = x,mp1[s] = i;
		else if(mp[s] > x) mp[s] = x,mp1[s] = i;
	}
	dfs(1,0);
	if(f[1][0] >= 1e15) f[1][0] = -1;//无解 
	print(f[1][0]);  flush(); 
	if(t == 1 && f[1][0] != -1) 
	{
		pc('\n');
		print(v[1][0].size()),pc('\n');
		for(int i = 0;i < v[1][0].size();i++)
			print(v[1][0][i].first),pc(' '),print(v[1][0][i].second.first),pc(' '),print(v[1][0][i].second.second),pc('\n'); 
		flush(); 
	}
	return 0;
}
/*
f_i_j以i为子树，向上j个最小花费 
*/