A

原题

题目大意

一棵有根树，每个边权重为1或0，两个人轮流走往前走一步，甲先，将经过的边的权重记下，直到无路可走，最后形成一个由0和1组成的字符串，根据其长度l，乙最多可以将蛋糕分为l个，然后对于字符串从头开始，当字符串第i个位置是1，则甲挑一块蛋糕，否则乙挑一块蛋糕。

两个人都想要拿到更多的蛋糕，即两个人都会实施最优策略

分析一下，对于该字符串，因为乙来分的蛋糕，所以他会选取一个起点固定为0，长度任意的字串，使得在该字串内0的比例最大

例：0111，乙只切成一块，乙就能拿走整个蛋糕，10011111，乙切成3块，能拿走2/3块蛋糕。

所以我们要做的是对于每个节点，如果是乙走，则他会找0比例最大，或者说1比例最小的子节点记录为最优策略，如果甲走，则他会找1比例最大，或者说0比例最小的子节点记录为最优策略。

代码

#include<bits/stdc++.h>
using namespace std;
#define MAX 200020
#define ll long long
#define inf 1e9
vector<int > p[MAX];//存储节点信息
vector<int > w[MAX];//存储边的权重
int f0[MAX], f1[MAX];//存储0，1的数量
double value1[MAX];//存储1的比例，在回溯过程中，作为最优策略去更新，最后value1[x]是最终答案
double value0[MAX];//存储0的比例，在深搜过程中，记录当前路径的结果，最后的节点才是当前路径的最终值
int h[MAX];//存储深度
void dfs(int x,int last)
{
    if (x != 1)value0[x] = max(value0[x] ,1.0 * f0[x] / (1.0 * (f1[x] + f0[x])));//因为乙会尽量让甲少拿，所以每次要更新为最大值。
    value1[x] = 1 - value0[x]; 
    bool flag = 0;


    int next;
    for (int i = 0; i < p[x].size(); i++)
    {
        next = p[x][i];//下个节点
        if (last == next) continue;//如果是爹，跳过
        h[next] = h[x] + 1;//更新深度
        f1[next] = f1[x];//前缀和？反正先继承上个节点的01数量
        f0[next] = f0[x];
        if (w[x][i] == 1) f1[next]++;//加上这个节点的01数量
        else f0[next]++;
        value0[next] = value0[x];//将下个节点的0占比先算成该节点的占比，因为0占比的最高值可能出现在中间
        dfs(next, x);//深搜
        if (!flag) value1[x] = value1[next], flag = 1;//如果是第一次循环，假设第一个节点即是最优解，方便直接比较
        if (h[x] % 2 == 0) value1[x] = min(value1[x], value1[next]);//乙使1的比例最小
        else value1[x] = max(value1[x], value1[next]);//甲使1的比例最大
    }
}
void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i <= n + 5; i++)//清空
    {
        while (p[i].size()) p[i].pop_back();
        while (w[i].size()) w[i].pop_back();
        f1[i] = 0;
        f0[i] = 0;
        
        value1[i] = 0;
        value0[i] = 0;
    }
    int u, v, k;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> u >> v >> k;
        //一定要存两遍！！！！！！！
        //我直接默认左边是爹右边儿子导致比赛的时候对着代码看了2个小时都没看出问题
        p[u].push_back(v);
        p[v].push_back(u);
        w[u].push_back(k);
        w[v].push_back(k);
    }
    h[1] = 1;//第一层深度记为一，则偶数是乙，奇数是甲
    dfs(1,1);
    cout << setiosflags(ios::fixed) << setprecision(11) << value1[1] << endl;//输出小数
}
int main()
{
    int t;
    cin >> t;
    while (t--)solve();
    return 0;
}

反思

1.首先是题目没看明白，测试点并不保证左边右边的父子关系

2.其次是这个更新答案的方法是从杭电那边copy的，感觉非常不错，很适合这个题目，01占比等价，那就一个深搜，一个回溯。