求助
查看原帖
求助
1090425
yehuadonghui楼主2024/5/27 11:35

基环树用并查集时这个取点时,为什么不能去这个点存在的情况啊? 当我分别以这两个点为根节点时,当不取到这个根节点的值时就过了

#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;
}
2024/5/27 11:35
加载中...