萌新刚学OI,求助!!!

P3806 【模板】点分治 1

bellmanford @ 2020-03-15 17:53:08

我一开始的找重心是这样子的:

void find_root(int u,int fa){
    size[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa||vis[v]) continue;
        find_root(v,u);
        size[u]+=size[v];
    }
    if(maxn>max(size[u],sum-size[u]))
        maxn=max(size[u],sum-size[u]),root=u;
}

void dfs(int u){
    calc(u,0,1);vis[u]=1;
    for(int i=first[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].val;
        if(vis[v]) continue;
        calc(v,w,-1);sum=size[u],maxn=1e9;
        find_root(v,u);dfs(root);
    }
}

实际上是在找u子树的重心而不是再找v子树的重心。

结果过了。。。

求助这是为何?


by function_of_zero @ 2020-03-15 18:06:29

@bellmanford 我找到了那篇博客,您看一下您写的是哪种吧


by bellmanford @ 2020-03-15 18:07:28

其实本题的第二篇题解也是这样写的。。。


by 辰星凌 @ 2020-03-15 18:08:25

Orz淀粉质巨佬


by bellmanford @ 2020-03-15 18:11:11

OrzFFT巨佬


by 梦寐茶禅斋 @ 2020-03-15 18:14:12

红名蓝勾大佬暴切紫题


by 45dino @ 2020-03-15 18:17:41

@bellmanford 红名蓝勾萌新,做我看都看不懂的题目……


上一页 |