## 牛客小白月赛45-E

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;
ll arr[maxn];
ll res = -0x3f3f3f3f;
int mark[maxn];
struct node {
int y;
ll w;
node(int a, ll b): y(a), w(b) {}
};
vector<node> v[maxn];
ll dfs(int rt, ll val) {
ll ans = 0;

for (auto to:v[rt]) {
node pos = to;
if (mark[pos.y])
continue;
mark[pos.y] = 1;
ll z = dfs(pos.y, pos.w);
if (z > 0)
ans += z;
}
res = max(res, ans + arr[rt]);
return ans + val + arr[rt];
}

int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
res = max(res, arr[i]);
}
int x, y;
ll w;
for (int i = 1; i < n; i++) {
cin >> x >> y >> w;
v[x].push_back(node(y, w));
v[y].push_back(node(x, w));
}
mark[1] = 1;
dfs(1, 0);
cout << res << endl;
return 0;
}

## 牛客练习赛97-D

\left\{\begin{aligned}dp[i][0]&=\prod(dp[son][0]\cdot x+dp[son][1]\cdot y)\\dp[i][1]&=\prod(dp[son][0]\cdot x+dp[son][1]\cdot(y-1))\end{aligned}\right.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod = 998244353;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
ll x, y;
cin >> n >> x >> y;
vector<vector<int>> G(n + 1);  // G最多放n+1个向量
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
function<pair<ll, ll>(int, int)> DFS = [&](int u, int p) {
pair<ll, ll> res{1, 1};
for (int v : G[u]) {
if (v != p) {
auto pr = DFS(v, u);
res.first = (pr.first * x + pr.second * y) % mod * res.first % mod;
res.second = (pr.first * x + pr.second * (y - 1)) % mod * res.second % mod;
}
}
return res;
};
auto pr = DFS(1, 0);
cout << (pr.first * x + pr.second * y) % mod << endl;
// system("pause");
return 0;
}