orz
by Petit_Souris @ 2021-11-16 15:56:10
@[fzj2007](/user/172370)
最后一段代码少了个右括号)
by fast_proton @ 2022-06-10 07:24:10
屑屑Orz
by comcopy @ 2022-07-24 16:50:04
奇怪,我这些点都注意到了,却还是 WA 第三个点 qwq <https://www.luogu.com.cn/record/81150160>
by Blunt_Feeling @ 2022-07-25 21:04:50
哦解决了,是因为第三个点他的树根不是 1,贴上 AC 代码(跟第一篇题解的 DP 思路不一样哦)
```cpp
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int maxn=1550;
int n,w[maxn],f[maxn][3]; //f[x][0/1/2]: x子树内部以处理好,x 没有被信号覆盖/有信号塔/被儿子信号塔覆盖
vector<int> g[maxn];
void dfs(int u,int fa)
{
f[u][1]=w[u];
for(int v:g[u])
{
if(v==fa) continue;
dfs(v,u);
f[u][0]+=min(f[v][1],f[v][2]); //?
f[u][1]+=min({f[v][0],f[v][1],f[v][2]}); //u自己有基站干啥都行
}
//此时相当于int sum=Σmin(f_v1,f_v2)=f[u][0]
int sum=f[u][0];
f[u][2]=INT_MAX;
for(int v:g[u])
{
if(v==fa) continue;
f[u][2]=min(f[u][2],f[v][1]+sum-min(f[v][1],f[v][2]));
}
}
bool vis[maxn];
int main()
{
cin>>n;
For(i,1,n)
{
int u; cin>>u;
cin>>w[u];
int o; cin>>o;
while(o--)
{
int v; cin>>v;
g[u].emplace_back(v);
vis[v]=true;
}
}
int rt;
For(i,1,n) if(!vis[i]) rt=i;
dfs(rt,rt); //rt的父亲应设为rt,因为再往上没人能救他
cout<<min(f[rt][1],f[rt][2])<<endl;
return 0;
}
```
by Blunt_Feeling @ 2022-07-25 21:09:22
@[Blunt_Feeling](/user/219866) plqtj?
by T_E_I_O_ @ 2022-09-27 17:41:18
但实际上影响答案的因素多半是第一条(id与i的混用),是否找出root影响不大,至少本人用1zuoroot就可以过(不过还是谢谢这篇警告)
by Fated_Shadow @ 2022-12-29 19:22:08