题解 [ZJOI2008] 骑士
hkr04
2019-11-07 21:00:53
[题目链接](https://www.luogu.org/problem/P2607)
先感谢题解区的各位！
如果它不是有 $n$ 条边，而是 $n-1$ 条边的话，它就是一棵树，也就是[没有上司的舞会](https://www.luogu.org/problem/P1352)。
现在只多了一条边，那它就是 **基环树**。相当于多了一个环，其他的结构没有很大的变化。至于对于基环树的处理，一般可以这么处理：
1. 找到环
2. 将环断开，让它成为一棵树，对于断开边的两个端点分别进行树形 dp。当然，需要注意一些关于这两个点的限制条件
3. 将信息整合，更新答案
需要注意的是，这里可能不只是一棵树，要对每个块进行相同的处理并加入到答案中。还要注意数据范围问题，需要开 `long long`。
对于本题的一般树形态，我们将状态设计为 $f_{i, 0/1
}$，表示对于以$i$为根节点的子树，该节点 **不选/选** 的时候的点权和最大值。因为 $i$ 和 $i$ 的子节点不能同时被选中，所以 $f_{i, 0}=\sum \max(f_{j, 0}, f_{j, 1})$($j$ 为 $i$ 的子节点）,也即当前点的子节点不受限制；$f_{i, 1}=\sum f_{i, 0}$，也即你选了我一定不能选我的子节点。对于一棵树的答案，就是 $\max(f_{\text{root}, 0}, f_{\text{root}, 1})$。
再来观察一下题目中基环树的形态，由于一个节点只会有一个仇恨的人，所以将我的仇人连向我。这个时候，每个点只连向另一个节点，建出来的一定是一棵 **外向树**。如下图：
不会出现有两条边指向同一个点的情况：
所以我们在找环的时候，一路回退，一定能找到当前基环树的环。
以上面那棵合法的举个例子，比如我发现 $7$ 号点没有被访问过，这说明这棵树的答案我还没有统计，从这个点开始往回到环上。过程如下：
当发现当前点的父亲已被遍历，说明当前点和它的父亲都在这个环上，强行将这条边断开，分别将其作为根节点进行处理。又因为这两个不能同时选，我们干脆就在处理 root 的时候，将它的 $f_{\text{root}, 1}$ 设为负无穷（遍历到时）。这样是不会影响最终答案的，是因为我们分别遍历的时候已经考虑了另一个未被设为根节点的点选或不选的情况了，可以避免同时被选的非法情况。每处理一次，就尝试更新 **当前树的答案**，处理完后将两种情况的最大值加入到总的答案中。
在向儿子节点遍历 **之前**，先设好边界条件，也就是$f_{i, 0}=0,f_{i, 1}=w_i$（当前点的点权）。记得你是要在一棵树中跑两次的，需要每次遍历之前都设好边界条件。
代码：
```cpp
#include <cstdio>
typedef long long ll;
const int maxn=1000000+10;
const ll INF=1LL<<60;
int head[maxn],to[maxn],nxt[maxn],fa[maxn];
int tot;
int root;
ll w[maxn],f[maxn][2];
ll ans;
bool vis[maxn];
ll max(ll x,ll y) {return x>y?x:y;}
void add(int u,int v)
{
nxt[++tot]=head[u];
head[u]=tot;
to[tot]=v;
}
void dfs(int u)
{
vis[u]=1;
f[u][0]=0,f[u][1]=w[u];
for (int i=head[u];i;i=nxt[i])
{
int v=to[i];
if (v!=root)
{
dfs(v);
f[u][0]+=max(f[v][0], f[v][1]);
f[u][1]+=f[v][0];
}
else
f[v][1]=-INF;
}
}
void FindCircle(int u)
{
vis[u]=1;
while(!vis[fa[u]])//因为入边唯一，这样一直往前找方便
{
u=fa[u];
vis[u]=1;
}
root=u;
dfs(u);
ll tans=max(f[u][0], f[u][1]);
u=fa[u];
root=u;
dfs(u);
ans+=max(tans, max(f[u][0], f[u][1]));
}
int main()
{
int n;
scanf("%d",&n);
for (int v=1;v<=n;v++)
{
int u;
scanf("%lld%d",&w[v],&u);
add(u, v);
fa[v]=u;
}
for (int i=1;i<=n;i++)
if (!vis[i])
FindCircle(i);
printf("%lld\n",ans);
return 0;
}
```