A.Cake
题意
两个人玩游戏，游戏分两阶段
第一阶段在一棵有根树上轮流走，走到叶子停止，有根树边上有 01 标记，记录下走过的 01 串
第二阶段分蛋糕，Oscar 按自己的意愿切蛋糕，然后按照第一阶段获得的 01 串顺序依次拿蛋糕（1 代表 Grammy 拿，0 代表 Oscar 拿）
两人都想让自己获得尽量多的蛋糕，求最后 Grammy 获得的蛋糕比例
分析
注意到是后手分蛋糕，然后观察样例，容易发现几个显然结论：如果第一步只有0，那么肯定只分一大块蛋糕，字符串开头是0，后手直接一步选完了。然后样例里面，字符串是10的话，后手会选择平均分，各拿一半。
然后就会猜，会不会是看前面有几个连续的1，然后对应平均分那么多份，到了0，就刚好拿走那一份分完。
不过很快就会有个反例，即11010000000000，最前面是110，如果平均分3份，显然是不如全部平均分，后手拿的会更多。
所以这样就可以看出来，似乎是看某个前缀的0占比最大，然后分这么多份，就可以让后手拿的最多。
发现这个结论后就很好写了，叶子节点的前缀最大0比值是确定的，每个结点根据当前是先手还是后手走，后手就往儿子中这个比值最大的地方走，先手则往这个比值最小的地方走。注意比值不一定要去分别存0和1的数量，可以存一个结点的深度和0的数量，两个的商就是占比。注意特判根节点深度为0，不要除以0.而且叶子结点不能单纯看边数是1确定，要在dfs里额外开一个变量，如果没有往儿子继续dfs的结点就是叶子结点。
点击查看代码
#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 998244353;
vector<pii> G[maxn];
db dp[maxn];
int dep[maxn];
void dfs(int u, int f, int tot) {
if (dep[u])
dp[u] = tot / (db)dep[u];
else
dp[u] = 0;
dp[u] = max(dp[u], dp[f]);
int cnt = 0;
for (auto [v, w] : G[u]) {
if (v == f)
continue;
cnt++;
dep[v] = dep[u] + 1;
dfs(v, u, tot + (w == 0));
}
if (!cnt)
return;
if (dep[u] & 1) {
dp[u] = 0;
for (auto [v, w] : G[u]) {
if (v != f)
dp[u] = max(dp[u], dp[v]);
}
} else {
dp[u] = 1;
for (auto [v, w] : G[u])
if (v != f)
dp[u] = min(dp[u], dp[v]);
}
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
G[i].clear();
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
dfs(1, 0, 0);
cout << fixed << setprecision(12) << 1 - dp[1] << "\n";
}
signed main() {
// freopen("2.in", "r", stdin);
// freopen("2.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}