这道题稍微想一想就会联想到树形DP的入门题：没有上司的舞会；
但是再想一想会发现这根本就不是一颗树，因为它比树多了一条边；
这时候我们引入一个新的概念：基环树；
顾名思义(??)，基环树就是在一颗树上填一条边构成的一个图；基环树也叫环套树（明明更像树套环）。
我们在树上可以做的事情基本都可以在基环树上实现：比如树形DP
基环树的基本解题思路就是找到在环上的两个点:S,T;
分别以S，T为根来跑一边DP，这样把两次的答案进行处理就可以解决掉这道题；
那么怎样找环？我总结了几种不同的思路：
1.并查集找环：对于要加入的两个点如果已经在同一个区域内，那么他们一定在环上；
2.tarjan找环：对于一个点，如果dfn[v]<dfn[u],那么u和v就在一个环上；
3.dfs找环:其实和tarjan的基本思路一样，如果一个点的子节点v已经被经过，那么u和v就在一个环上；
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct littlestar{
int to;
int nxt;
}star[2000010];
int head[2000010],cnt;
void add(int u,int v)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
head[u]=cnt;
}
int ha[1000010],fa[1000010];
int f[1000010],g[1000010],vis[1000010];
void dfs(int u,int goal)
{
vis[u]=1;
f[u]=ha[u];
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(v==goal){
f[v]=-999999999;
continue;
}
dfs(v,goal);
g[u]+=max(g[v],f[v]);
f[u]+=g[v];
}
}
int ans;
signed main()
{
int n; cin>>n;
for(register int i=1;i<=n;i++){
scanf("%d%d",&ha[i],&fa[i]);
add(fa[i],i);
}
for(register int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=1;
int root=i;
while(!vis[fa[root]]){
root=fa[root];
vis[root]=1;
}
dfs(root,root);
int tmp=max(g[root],f[root]);
vis[root]=1;
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
root=fa[root];
dfs(root,root);
tmp=max(tmp,max(g[root],f[root]));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
ans+=tmp;
}
}
cout<<ans;
}
然后可以双倍经验：洛谷 P1453 城市环路
#include <bits/stdc++.h>
using namespace std;
struct littlestar{
int to;
int nxt;
}star[200010];
int head[200010],cnt;
void add(int u,int v)
{
star[++cnt].to=v;
star[cnt].nxt=head[u];
head[u]=cnt;
}
int ha[100010],fa[100010];
double f[100010],g[100010];
void dfs(int u,int ff)
{
f[u]=ha[u];
g[u]=0;
for(int i=head[u];i;i=star[i].nxt){
int v=star[i].to;
if(v==ff){
continue;
}
dfs(v,u);
f[u]+=g[v];
g[u]+=max(g[v],f[v]);
}
}
inline int zhaobaba(int x)
{
if(fa[x]==x) return x;
return fa[x]=zhaobaba(fa[x]);
}
int S,T;
int main()
{
int n;
cin>>n;
for(register int i=1;i<=n;i++) scanf("%d",&ha[i]),fa[i]=i;
for(register int i=1;i<=n;i++){
int u,v;
scanf("%d%d",&u,&v);
++u;
++v;
if(zhaobaba(u)==zhaobaba(v)){
S=u;
T=v;
continue;
}
add(u,v);
add(v,u);
fa[zhaobaba(v)]=zhaobaba(u);
}
double ans=0,k;
scanf("%lf",&k);
dfs(S,0);
ans=g[S];
dfs(T,0);
ans=max(ans,g[T]);
printf("%.1lf",ans*k);
}