蒟蒻关于点分治找重心的一个小问题

P3806 【模板】点分治 1

EndSaH @ 2019-01-06 13:09:33

对于这样的一张图:

以第一篇题解为例:

void solve(int u)
{   
    //judge[i]表示到根距离为i的路径是否存在
    vis[u]=judge[0]=1; calc(u);//处理以u为根的子树
    for(int i=head[u];i;i=E[i].nxt)//对每个子树进行分治
    {
        int v=E[i].v;
        if(vis[v])continue;
        sum=size[v]; maxp[rt=0]=inf;
        getrt(v,0); solve(rt);//在子树中找重心并递归处理
    }
}

maxp[rt]=sum=n;//第一次先找整棵树的重心
getrt(1,0); 
solve(rt);//对树进行点分治

getrt(1,0)中, 可以求出重心为2号结点.

但是在solve函数前面的计算执行完之后的过程中:

sum = size[v]; maxp[rt = 0] = inf;
getrt(v, 0); solve(rt);

v为1, 因为一开始getrt(1, 0)相当于算出以1为根时各个节点的size, 那么此时的size[v]仍为13.

这与点分治的思路并不相符(此时正确的size[1]应当为以2为根时的size, 即6), 很有可能导致接下来递归求重心的过程中出现错误.

但是我看很多题解都是这么打的, 请问一下dalao们, 这样做的缘由是什么?

(如果要打我的脸的话请轻一点emm)


by cloud_9 @ 2019-01-06 13:15:18

ORZ_{Au}boye

by GNAQ @ 2019-01-06 14:16:02

我没仔细看,可能是错的,但是实际上如果你

  1. 第一次分治求对重心

  2. 后面分治以玄学方法求错误的重心 或者 随机重心

只要写的是对的,可以过大部分点分题的很多数据


by 八水L @ 2019-02-17 19:55:33

@HNYLMS_EndSaH 你说得好像有道理,实在不行再加个函数专求siz吧


by 八水L @ 2019-02-17 20:00:30

@HNYLMS_EndSaH 在递归求答案的函数里加就可以了


by EndSaH @ 2019-02-17 20:58:28

@㵘㵘酱 是的,我后来也是这么打的


by 天朝理科生 @ 2019-03-21 21:56:41

看了dalao的讨论豁然开朗

话说dalao为什么都说自己的蒟蒻

这让我这个真正的蒟蒻怎么办


by EndSaH @ 2019-08-21 11:27:20

@niiick


by EndSaH @ 2019-08-21 11:31:35

@Ender_zzm 你的貌似也是这样


by Holy_Push @ 2019-08-21 11:39:03

我就是直接重新打一个求size的过程,因为题解里那种我看不懂QwQ(其实我也觉得有点不对)


by Holy_Push @ 2019-08-21 11:40:28

不过其实玄学求错误重心,只要错的不是太离谱,在数据不是很卡的情况下应该没多大问题


| 下一页