背景故事：《讨论：为什么vector会比数组快》

今天在做这道题，的时候用了vector存图，发现跑不过邻接表了

///***********
vector存图18秒
************//
#include<bits/stdc++.h>
using namespace std;
int n,k,ans,is=1;
vector<int> g[1000005];
int dfs(int x,int fa){
	if(g[x].size()==1)return 1;
	int len=0;
	for(int i=0;i<g[x].size();i++){
		if(g[x][i]==fa)continue;
		int d=dfs(g[x][i],x);
		if(d+len>k)ans++,len=min(len,d);
		else len=max(len,d);
	}
	return len?len+1:0;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	for(int i=1;i<=n;i++)if(g[i].size()>1){
		is=dfs(i,i);
		break;
	}
	printf("%d",ans+(is>0));
	return 0;
}

//************
邻接表存图10秒
************//
#include<bits/stdc++.h>
using namespace std;
int n,k,ans,is=1;
int du[1000005],to[2000005],ne[2000005],f[1000005],cnt;
inline void link(int x,int y){
	to[++cnt]=y;
	ne[cnt]=f[x];
	f[x]=cnt;
}
int dfs(int x,int fa){
	if(du[x]==1)return 1;
	int len=0;
	for(int i=f[x];i;i=ne[i]){
		int u=to[i];
		if(u==fa)continue;
		int d=dfs(u,x);
		if(d+len>k)ans++,len=min(len,d);
		else len=max(len,d);
	}
	return len?len+1:0;
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		link(x,y);du[x]++;
		link(y,x);du[y]++;
	}
	for(int i=1;i<=n;i++)if(du[i]>1){
		is=dfs(i,i);
		break;
	}
	printf("%d",ans+(is>0));

	return 0;
}

是只有在bfs时，vector才会比邻接表快吗