基环树用并查集时这个取点时,为什么不能去这个点存在的情况啊? 当我分别以这两个点为根节点时,当不取到这个根节点的值时就过了
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int>
#define vi vector<int>
#define si set<int>
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
#define is insert
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
const int INF =1e9;
const int N = 100010;
int a[N],p[N],vis[N];
int n,rt1,rt2,idx;
int e[N*2],ne[N*2],h[N*2];
int f[N][2];
int find(int x)
{
if(p[x]!=x){
p[x]=find(p[x]);
}
return p[x];
}
void add(int x,int y){
e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}
void circle(int x,int fa){
f[x][1]=a[x],f[x][0]=0;
for (int i=h[x];~i;i=ne[i]){
int j=e[i];
if(j==fa){
continue;
}
circle(j,x);
f[x][1]+=f[j][0];
f[x][0]+=max(f[j][0],f[j][1]);
}
}
signed main()
{
memset(h,-1,sizeof h);
cin>>n;
for (int i=1;i<=n;i++){
cin>>a[i];
p[i]=i;
}
for (int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
x++,y++;
if(find(x)==find(y)){//成环。
rt1=x,rt2=y;
continue;
}
add(x,y),add(y,x);
p[find(y)]=find(x);
}
double k;
cin>>k;
double ans1=0,ans2=0;
circle(rt1,0);
ans1=f[rt1][1];
circle(rt2,0);
ans2=f[rt2][1];
cout<<fixed<<setprecision(1);
cout<<max(ans1,ans2)*k;
}