题目难度与顺序无关

T1

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int s, n, a[N], f[N];
vector<int>e[N];

bool cmp(int x, int y) {
	return f[x] > f[y];
}

void dfs(int x, int fa) {
	vector<int>cnt;
	for (auto v : e[x]) {
		if (v == fa || a[v] == 0)
			continue;
		dfs(v, x);
		cnt.push_back(v);
	}
	sort(cnt.begin(), cnt.end(), cmp);
	for (int i = 0; i < cnt.size(); i++) {
		int v = cnt[i];
		if (x != s && a[x] >= 2 && f[v] != 0) {
			f[x] += f[v];
			f[x] += 2;
			a[x]--;
			a[v]--;
		}
		if (x == s && a[x] >= 1 && f[v] != 0) {
			f[x] += f[v];
			f[x] += 2;
			a[x]--;
			a[v]--;
		}
	}
	for (auto v : e[x]) {
		if (v == fa)
			continue;
		if (x != s && a[x] > 1) {
			f[x] += min(a[v], a[x] - 1) * 2;
			a[x] -= min(a[v], a[x] - 1);
			a[v] -= min(a[v], a[x] - 1);
		} else if (x == s && a[x] > 0) {
			f[x] += min(a[v], a[x]) * 2;
			a[x] -= min(a[v], a[x]);
			a[v] -= min(a[v], a[x]);
		}
	}
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	cin >> s;
	dfs(s, 0);
	cout << f[s] << endl;
	return 0;
}