Codeforces Round 614

题目

https://codeforces.com/contest/1292/problem/C

2300评分

大意

给树的形状，你需要把0到n-2分别填在边上。

求 sum{mex{所有简单边}}的最大期望值

数据范围

节点数小于3000

3s

512MB

题解

官方题解

感觉对mex的题始终不会

$S = \sum_{1 \leq u < v \leq n} mex(u, v) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) = x} mex(u,v) \right) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) = x} x \right) = \sum_{1 \leq x \leq n} \left( \sum_{mex(u, v) \geq x} 1 \right) = \sum_{1 \leq x \leq n} f(x)$

直接解读这个公式。

第一个等式是定义

第二个第三个等式是按照mex的值进行拆分，

第四个等式的转换是 $x = \sum_{1\leq y \leq x} 1$,也就是原来在x时增加 $sum mex$ 倍 $x$,改为 从1 到x，各增加 sum mex倍 1

最后一个等式是定义 f(x)函数

$f(x) = count(mex(u,v) \ge x) =$ 包含 [0 ->x-1]的简单路径数量

---

证明叶子到叶子包含0到len-1

考虑一个树的形成过程如果是从0到n-2的放置，如果当前0到x-1已经固定，准备放x，那么只有把它放在0到x-1所有都在的路径上（如果可能），才能产生更大的mex，如果不这样，那么x以及所有大于x的最后的mex都已经固定。

因此放置时如果能够放到0到x-1的路径上，则一定是放在路径上。

也就意为这 一定有一条从叶子到叶子的简单路径 放了 0到length-1, 并且剩余的无论怎么放(因为已经叶子到叶子，不可能再集齐0到i了，mex也就不会变了) 对结果都没有影响

---

证明这条路径上赋值山谷形状

现在假设固定了简单路径的位置，下面要证明最优值的放置 是山谷形状，也就是 a1>a2>…>ap<…<al−1<al.

假设，[0->x-1]是连续的一段，x和这一段不连续 不妨设x在这一段的右侧（否则就左侧）

? ? ? ? [0到x-1连续的一段] vali ? ? ? ? ? x ? ? ? ?

我们交换 vali和x的位置

显然，对于f(0->x-1)不会变 因为 连续段的位置没有改动，也就是包含[0->x-1]的简单路径数量不变

对于f(x)变大，因为包含[0->x]的 简单路径数量 = 连续段左侧分支数量 * x右侧分支数量，乘法第一个值不变，第二个值变大，总的值一定变大

对于f(>x) 不减， 对于左侧点位置不变，对于右侧点不变或者有更进的右侧点，所以包含[0->(>x)]的 简单路径数量 = 连续段左侧分支数量 * x右侧分支数量，乘法第一个值不变，第二个值不减，总的值一定不减

总的来说，如果不满足上述状态，则一定有一个更优的摆放方法。综上，一定是山谷形

---

然后就有了dp[u][v] = $\sum_{1 \leq x \leq l} f(x)$的最大值，且u到v 填写的是0到l-1

定义(方便描述)

par(r,u): 以r为树的根节点，u的父节点

sub(r,u), 以r为树的根节点，u的子树的节点个数

官方题解的解释图

---

计算dp[u][v],根据我们的山谷原理，和dp的定义，dp[u][v]的最大值一定在两端的某一端

所以 剩余的部分为dp[u][par(u,v)] 或者 dp[par(v,u)][v],又dp只关心f(<=l),所以剩余只有f(l)要计算

这显然 f(l) = sub(u,v) * sub(v,u)

$dp[u][v] = sub(u, v) \times sub(v, u) + \max(dp[par(v, u)][v], dp[u][par(u, v)])$

一个点的所有分支子节点 直接dfs，对于父方向的= 总量-1-子分支即可，也就是每个点各个分支子节点数O(n)计算完，要计算一个具体sub时可以O(1)计算

对于par，我们可以把dp改为递推即可，

代码

TLE14

去掉map WA17

int 改 long long Accept

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);

// 树,边被赋值[0,n-2]
// 输入n 3000
// 树状

int n;
vector<int>p2[3010];

map<int,int>chcnt[3010];// child cnt [idx][p2] = childcnt

vector<pair<int,int> > cur; // [u<v] = [par,par,sum]
tuple<int,int,ll>cost[3010][3010]; // [u<v] = [par,par,sum]

int initchcnt(int idx,int fa){
  int cnt = 1;
  for(auto item:p2[idx]){
    if(item == fa)continue;
    cnt+= (chcnt[idx][item] = initchcnt(item,idx));
  }
  if(fa){
    chcnt[idx][fa] = n - cnt;
  }
  return cnt;
}

ll cnt(int u,int paru){
  return n-chcnt[u][paru];
}
ll ans = 0;

// u pvu .... puv v
void addrel(int u,int v,int pvu,int puv,ll count){
  if(u > v){
    swap(u,v);
    swap(pvu,puv);
  }
  ll newcount = count + cnt(u,pvu)*cnt(v,puv);
  ans=max(ans,newcount);
  if(get<2>(cost[u][v])==0){
    cur.pb({u,v});
  }
  if(get<2>(cost[u][v]) < newcount ){
    cost[u][v] = {pvu,puv,newcount};
  }
}

int main(){
  cin>>n;
  rep(i,0,n-1){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].pb(v);
    p2[v].pb(u);
  }
  initchcnt(1,0);
  // 减少重复运算u<v
  // 按照length递增 广搜
  rep(i,1,n+1){
    for(auto item:p2[i]){
      if(item < i)continue;
      addrel(i,item,item,i,0);
    }
  }
  rep(i,0,cur.size()){
    auto [u,v] = cur[i];
    auto [pvu,puv,count] = cost[u][v];
    // u pvu .... puv v
    // 扩展u
    for(auto nu:p2[u]){
      if(nu == pvu)continue;
      addrel(nu,v,u,puv,count);
    }
    // 扩展v
    for(auto nv:p2[v]){
      if(nv == puv)continue;
      addrel(u,nv,pvu,v,count);
    }
  }
  printf("%lld\n",ans);

  return 0;
}

总结

看到max，min有可能去考虑贪心或者说局部最优，比如这里的 山谷形状

mex是真的自闭

n看到了3000就算想到了n方dp，没想到上面这些证明也没卵用