Atcoder abc291

https://atcoder.jp/contests/abc291/tasks

Ex - Balanced Tree

给定n点树T

构建n点新的有根树R满足

• lca(u,v) 在 T中的path(u,v)上

• 所有非根点u, 2sz[u] <= sz[fa[u]]

(题目保证有解)

输出R

n 1e5

2s

1024mb

我的思路

显然 性质2说明所有向下分叉至少是2叉

---

性质一怎么用?

如果在R中u是v的祖先节点

lca(u,v) = u

u一定在路径T(u,v)上

…

v1,v2 在 u 两个分支, lca(v1,v2) = u

u要在(v1,v2) 路径上

…

如果u选作 R的根, 那么在T 中u的一个分支中的所有点一定在R中也是同一个分支中

所以要在T中找一个点，使得它的所有分支的点数 * 2 都 <= n

注意到 任意点最多一个分支 点数 * 2 > n, 所以沿着这个方向走，这个方向的点数单调递减

而 …-u-(v > n/2), 则从选择u移动到选择v: (…-u < n/2)-v-(…)

所以总可以找到一个点

那么选作为根以后，直接按它切开，剩余的连通块就是子问题了

---

但是如何 优化每次寻找?

还是直接暴力复杂度就够了

注意到第一次是O(n)

那么第二次每个块 <= n/2, 而总复杂度依然是O(n)

所以 O(n log n) 暴力就没了

---

写完以后发现，不一定是 所有二叉，因为 两点的话 ，叶子是1, 带叶子的一个是2也是合法的，所以二不二叉不重要，重要的是所有分叉 <= n/2

代码

https://atcoder.jp/contests/abc291/submissions/41836648

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}

vector<int> e[100010];
int ans[100010]; // ans[]=0表示 还未选中为某个根
int sz[100010];

int dfs(int u,int f,int tot){ // u, T中的fa, 块大小
  int ret = 0;
  sz[u]=1;
  bool pick = true;
  for(auto v:e[u]) if(v!=f and !ans[v]){
    int r = dfs(v,u,tot); // 需要更新sz, 所以始终要dfs
    if(ret == 0) ret = r;
    sz[u]+=sz[v];
    if(2*sz[v] > tot) pick = false; // 所有子 <= tot
  }
  if(2*(tot - sz[u]) > tot) pick = false; // 所有 <= tot
  if(pick) ret = u;
  return ret;
}

void solve(int u,int tot,int f){ // u, 块大小, R中的father
  int r = dfs(u,-1,tot);
  ans[r] = f;
  for(auto v:e[r]) if(!ans[v]) solve(v,(sz[v] < sz[r])?sz[v]:(tot-sz[r]),r);
}

int main(){
  int n=read();
  rep(i,1,n){
    int u=read();
    int v=read();
    e[u].push_back(v);
    e[v].push_back(u);
  }
  solve(1,n,-1);
  rep(i,1,n+1) printf("%d ",ans[i]);
  return 0;
}

总结

不愧是 黄题的 G和Ex, 没啥难度

参考

官方题解