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 红名蓝勾萌新,做我看都看不懂的题目……