题解 | #Cake#_牛客博客

思路：

（1）. 对于第二阶段是由Oscar进行切割且可以存在为空的蛋糕块，所以站在Oscar的角度，当他获得一个01串时，它可以找到该串0的占比（设为 p）前缀最大的位置，将该位置后面的所有的份划分成为空的蛋糕块，然后前面份进行平分蛋糕，Oscar获得其中他所占有份额（也就是0在该前缀的占比）。

（2). 对于第一阶段，我们首先要知道，对于每一个叶子节点都只会存在一条路径经过他（树型结构），所以当我们 dfs 到叶子节点后，代表一个执行方案（路径）的结束。结合（1）我们可以通过dfs的形式维护每一条路径中 0 的最大前缀占比（或者 1的最小前缀占比）是多少（该值最后存于叶子节点当中）。接着在回溯的时候根据执行对象是Oscar 还是 Grammy 进行不一样的操做。如果轮到 Grammy 则选择占比小的那条路径，Oscar则相反（也就是从叶子节点到根节点dp）,每次就不同角色选择不同的路径，当维护到根的时候则是答案。

      #include <iostream>
      #include <algorithm>
      #include <cmath>
      #include <cstring>
      #include <vector>
      #include <cmath>
      #include <stack>
      #include<unordered_map>
      #include<set>
      #include<map>
      #include <queue>
      
      using namespace std;
      
      const int N = 2e5 + 10, M = 998244353;

      #define x first
      #define y second

      typedef long long ll; 
      typedef pair<int, int> pii;
      
      double f[N];
      vector<pii> head[N];

      //cnt : 走到该点一共经过了多少个 0
      //num : 走到该点一共经过了多少个边
      void dfs(int root, int fa, int cnt, int num) {

      //维护走到该点位置 0 的最大前缀占比
         if(num) f[root] = max(f[fa], 1.0 * cnt / num);
             
         for(auto u : head[root]) {
            if(u.x != fa) {
               dfs(u.x, root, cnt + (u.y == 0), num + 1);
            }
         }
         
         //叶子节点直接跳过
         if(head[root].size() == 1 && fa != - 1) return;
 
         //回溯是就执行对象不同，走不同的路 num % 2 == 0 代表 Grammy
         if(num % 2) f[root] = - 1;
         else f[root] = 1e9;
         
         for(auto u : head[root]) {
            if(u.x == fa)  continue;
            
            if(num % 2) 
               f[root] = max(f[root], f[u.x]);
            else
               f[root] = min(f[root], f[u.x]); 
         }
      }

      void Solved()
      {
          int n;
          cin >> n;

          for(int i = 1; i <= n; i ++) head[i].clear();

          for(int i = 1; i <= n - 1; i ++) {
            int a, b, w;
            cin >> a >> b >> w;
            head[a].push_back({b, w});
            head[b].push_back({a, w});
          }
          

          f[1] = 0;
          dfs(1, - 1, 0, 0);

         printf("%.12lf\n", 1 - f[1]);
      }

      int main()
      {
      
         ios::sync_with_stdio(false);
         cin.tie(0);
         cout.tie(0);


         int t;
         cin >> t;
         //t = 1;
      
         while (t --)
         {
            Solved();
         }
         return 0;
      }

题解 | #Cake#

思路 ：

思路：