几个月前我是这么写的,能过R118322717。
void dfs(int d,int f,int u){
dep[u]=d;
fa[u]=f;
size[u]=1;
int soc=-1;
for(int i=h[u];i;i=e[i].u){
int v=e[i].v;
if(v!=f){
dfs(d+1,u,v);
size[u]+=size[v];
if(size[v]>soc){
son[u]=v;
soc=size[v];
}
}
}
}
最近复习,想优化一下,写成这样。
void dfs(int u){
dep[u]=dep[fa[u]]+1;
size[u]=1;
for(int i=h[u];i;i=e[i].u){
int v=e[i].v;
if(v!=fa[u]){
fa[v]=u;
dfs(v);
size[u]+=size[v];
if(size[v]>son[u])son[u]=v;
}
}
}
却直接 T 了 3 个点,R148486659。
测试了一下,发现是把 soc 删掉之后 T 的,即使只是把 soc 放在 for() 里都会慢将近 200ms,R148486941。
这是为啥,访问数组比访问变量更慢吗?