D. Kay and Snowflake 树的重心-白红宇

D. Kay and Snowflake 树的重心

阅读量：5035 次

发布时间：2019-06-12

本文共 2088 字，大约阅读时间需要 6 分钟。

给出q个询问，每次要求询问以x为根的子树中，哪一个点是重心。

树的重心：求以cur为根的子树的重心，就是要找一个点，使得删除这个点后，分开来的零散的子树中，节点数的最大值最小。并且最大值最多也只是son[cur] / 2，因为最坏情况（最难分）也就是一条直线，选中间点就可以了。

例如

询问1的时候，就应该删除3，然后得到4个零散分支，2个大小是1,2个是2。

算法思路：

直观来说，应该是删除那个儿子数最多的那个节点的。比如上图，3的儿子数最多，所以询问1就删除3了。因为，没理由再分一些节点给最大的那颗子树把，这样只会更坏。

但是却可以把最大的那颗子树分一些节点去另一边，所以优先删除最大的那颗子树的重心，然后判断是否符合要求，不符合就只能暴力往上找了。

判定条件是son[cur] > 2 * son[重心]就不行。

因为这表明son[cur] - son[重心]的值还大于son[cur] / 2

代进去就知道了son[cur] - son[重心] > son[重心]，

假设son[cur] = 2 * son[重心]。那么就是剩下的节点数会大于son[cur] / 2咯。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 const int maxn = 300000 + 20;int ans[maxn];int son[maxn]; //第u个点有多少个儿子。int fa[maxn]; //记录第i个点的爸爸是谁struct node { int u, v, tonext;}e[maxn];int first[maxn];int num;void add(int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].tonext = first[u]; first[u] = num;}void dfs(int cur, int from) { son[cur] = 1; //自己一个 ans[cur] = cur; //叶子节点 int mx = -inf, pos = cur; //以这个点为子树的儿子数最多的那个pos for (int i = first[cur]; i; i = e[i].tonext) { dfs(e[i].v, cur); son[cur] += son[e[i].v]; //加上儿子的节点个数 if (mx < son[e[i].v]) { //不能算自己，只能算儿子的max mx = son[e[i].v]; pos = e[i].v; //儿子数最多的那个节点， } } ans[cur] = ans[pos]; //ans[pos]已经算出来了，ans[pos]的重心 while (son[cur] > 2 * son[ans[cur]]) { ans[cur] = fa[ans[cur]]; //暴力往上找 }}void work() { int n; cin >> n; int q; cin >> q; for (int i = 2; i <= n; ++i) { int x; cin >> x; add(x, i); fa[i] = x; } dfs(1, -1); for (int i = 1; i <= q; ++i) { int x; cin >> x; cout << ans[x] << endl; }}int main() {#ifdef local freopen("data.txt","r",stdin);#endif IOS; work(); return 0;}

重心的定义是：

找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡

(一)

树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么他们的距离和一样。

(二)

把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。

(三)

把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

转载于:https://www.cnblogs.com/liuweimingcprogram/p/6031706.html

你可能感兴趣的文章