找环方法

dfs并标记和存储到栈里， 若找到一个已经标记过的点就停止，然后将栈里的点在特判，若出度为1（只判断栈里的点，并非全部点），就标记不在环内，出度为2，则在环内

环状dp 假设

#include<bits/stdc++.h>
#define SIZE (100000+10)
using namespace std;
bool vis[SIZE];/*标记*/
int w[SIZE];/*权值*/
int f[SIZE][2];/*dp*/
int t[SIZE][2];/*辅助dp*/
int s[SIZE];/*栈*/
int top;/*top指针*/
int len;/*环上点的个数*/
vector <int> root;/*环上点*/
vector <int> son[SIZE];/*儿子*/
bool dfs(int x,int fa)
{
	s[++top]=x;
	vis[x]=true;
	for(int i=0;i<son[x].size();i++)
	{
		int v=son[x][i];
		if(v!=fa&&(vis[v]||dfs(v,x)))
		 return true;
	}
	--top;
	vis[x]=false;
	return false;
}
void dp(int x,int fa)
{
	f[x][1]=w[x];
	for(int i=0;i<son[x].size();i++)
	{
		int v=son[x][i];
		if(v!=fa&&!vis[v])
		{
			dp(v,x);
			f[x][0]+=max(f[v][0],f[v][1]);
			f[x][1]+=f[v][0];
		}
	}
}
int cdp(int k)
{
	memcpy(t,f,sizeof(t));
	t[root[1]][k]=-0x3f;
	for(int i=2;i<=len;i++)
	{
		int x=root[i];
		int y=root[i-1];
		t[x][0]+=max(t[y][0],t[y][1]);
		t[x][1]+=t[y][0];
	}
	if(!k) return t[root[len]][0];
	return max(t[root[len]][0],t[root[len]][1]);
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 scanf("%d",&w[i]);
	for(int i=1,u,v;i<=n;i++)
	{
		scanf("%d%d",&u,&v);
		++u,++v;
		son[u].push_back(v);
		son[v].push_back(u);
	}
/*---------找环--------*/
	dfs(1,-1);
    /*去除非环上点*/
	for(int i=1;i<=top;i++)
	{
		int cnt=0;
		for(int j=0;j<son[s[i]].size();j++)
		 cnt+=vis[son[s[i]][j]];
		if(cnt==1)
		 vis[s[i]]=false;
	}
    /**/
	root.push_back(0);
	for(int i=1;i<=n;i++)
	 if(vis[i])
	  root.push_back(i);
	len=root.size()-1;
/*------------------*/
//	for(int i=1;i<root.size();i++)
//	 printf("%d ",root[i]);
//	printf("\n"); 
/*--------以每个环上的点为根dp--------*/
	for(int i=1;i<=len;i++)
	 dp(root[i],-1);
/*处理环dp（假设）
cdp(1) 环上节点1不选
cdp(0) 环上节点1选
*/
	int ans=max(cdp(1),cdp(0));
	double k;
	scanf("%lf",&k);
	printf("%0.1lf",k*ans);
	return 0;
}
/*
12
2 8 8 10 3 3 5 2 1 3 8 9
1 5
12 1
9 1
9 8
9 7
11 7
12 10
4 2
4 3
4 1
6 2
7 8
1
*/

很痛苦，若是我思想错了，求指出（T_T）