关于基环树的东西。
一些知识
- 基环树：树加上一条边。点数和边数相同。它是图。可看作环上挂着一些树。
- 基环内向树：环上挂着的树的树根指向环。
- 基环外向树：环内节点指向环上挂着的树的树根。
- 解决方案：枚举环上断点、断边。
P5022 [NOIP2018 提高组] 旅行
题意
任意选定一个城市作为起点，然后从起点开始，每次可以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。当回到起点时，可以选择结束这次旅行或继续旅行。需要注意的是，在旅行方案中，每个城市都被访问到。求字典序最小的旅行方案。城市数 ，道路数等于城市数或城市数减一。
题解
对于道路数等于城市数减一：以城市 为起点，跑 dfs 遍历，优先选择城市编号小的 dfs。
对于道路数等于城市数：找到环，枚举断边（因为总有一个边不走），同上，取最优。
并没有代码。
P2607 [ZJOI2008]骑士
题意
基环树 + 树上最大独立集。节点数 。
题解
由于每人只厌恶一人，可以证明，森林中每棵树最多有一个环（这里的“树”可指基环树）。将厌恶骑士 的那个骑士 ，作为 的儿子节点，构建基环外向树森林。
找到环，取一条边。由于环上的任意一条边，它的两个端点至少有一个不取，所以分别以这条边的两个端点为根节点，进行 没有上司的舞会(); 。注意，分别进行 没有上司的舞会(); 时，另一个端点是一定不能选的。取两者答案最大值。
注意，可能图不连通。因此答案取总和。
代码
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=1000000+10;
int n,root,r[N],head[N],cnt=0,dad[N],v[N];
long long f[N][2],ans=0,tmp1=0,tmp2=0;
struct edge{int nxt,to;}e[N*2];
void add(int x,int y){e[++cnt]=(edge){head[x],y};head[x]=cnt;}
void dfs(int now,int del)
{
f[now][1]=r[now];f[now][0]=0;v[now]=1;
for(int i=head[now];i;i=e[i].nxt)
{
int to=e[i].to;
if(to==del) {f[to][1]=-N;continue;}
dfs(to,del);
f[now][0]+=max(f[to][1],f[to][0]);
f[now][1]+=f[to][0];
}
}
void getring(int root)
{
while(!v[root])
v[root]=1,root=dad[root];
tmp1=0;dfs(root,root);
tmp1=max(f[root][0],f[root][1]);
tmp2=0;dfs(dad[root],dad[root]);
tmp2=max(f[dad[root]][0],f[dad[root]][1]);
ans+=max(tmp1,tmp2);
}
void yzmain()
{
int t;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",r+i,&t);
add(t,i);dad[i]=t;
}
for(int i=1;i<=n;i++)
if(v[i]==0) getring(i);
printf("%lld\n",ans);
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/e4d084796bdd/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
