题解：P11179 [ROIR 2018 Day1] 管道监控
kkxacj
·
·
题解
前言
应发电机要求，感谢发电机发的电和思路。
思路
根据题目描述，我们需要遍历的点是一条从祖先到儿子的链，但如果这样覆盖就不好统计哪些点未遍历，考虑反过来，即以从儿子到祖先的方式来遍历，这样只需要保证以 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}
合并完后，一直跳祖先得到一个字符串，若有这种操作，就尝试更新。
对于判无解情况，我们可以给初值赋为一个很大的数，若最终值大于等于这个很大的数，就说明无解。
给出 $t=0$ 的代码供参考[look](https://www.luogu.com.cn/paste/wlwuemy1)。
对于 $t=1$，我们可以开 `vector` 来记录，$v_{i,j}$ 表示在此状态下的操作集合，在合并时，记录一下从哪两个地方转过来的，在最后合并就可以保证复杂度正确，合并完后的操作也同理。
**code**
```cpp
#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个最小花费
*/
```