题解：
n== m很容易可以知道这是个基环树
记录环的起点终点，跑dp。
dp还是挺简单的。
#include#include #include #include #define N 1000007using namespace std;int n, x, y, p[N], head[N], tot;bool flag[N], flag1;double dp[N][2], k, ans;struct node { int to, nxt;} edge[N << 1];void add_edge(int u, int v) { edge[++tot].to = v, edge[tot].nxt = head[u], head[u] = tot; edge[++tot].to = u, edge[tot].nxt = head[v], head[v] = tot;}void dfs(int now, int fa) { dp[now][1] = p[now], dp[now][0] = 0; for(int i = head[now]; i; i = edge[i].nxt) if(edge[i].to != fa) { dfs(edge[i].to, now); dp[now][0] += max(dp[edge[i].to][0], dp[edge[i].to][1]); dp[now][1] += dp[edge[i].to][0]; }}int main() { scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &p[i]); for(int i = 1, u, v; i <= n; ++i) { scanf("%d%d", &u, &v); u = u + 1, v = v + 1; if(!flag1 && flag[u] && flag[v]) { flag1 = 1, x = u, y = v; continue; } flag[u] = flag[v] = 1; add_edge(u, v); } scanf("%lf", &k); dfs(x, x); ans = dp[x][0];// for(int i = 1; i <= n; i++) printf("%.1lf %.1lf\n ", dp[i][1], dp[i][0]); dfs(y, y); ans = max(ans, dp[y][0]);// for(int i = 1; i <= n; i++) printf("%.1lf %.1lf\n ", dp[i][1], dp[i][0]); printf("%.1lf", ans * k); return 0;}
一世安宁