U193485 求助
  • 板块学术版
  • 楼主IYSY2009I
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/12/19 12:07
  • 上次更新2023/10/28 14:06:13
查看原帖
U193485 求助
449457
IYSY2009I楼主2021/12/19 12:07

RT,0分代码,样例能过

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,q;
int ans[100005];
int dis[100005];
int disa[100005];
bool vis[100005];
struct edge{
	int nxt;
	int to;
	int v;
};
edge e[200005];
int h[100005];
int cnt;
void add(int x,int y){
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=h[x];
	h[x]=cnt;
	return;
}
void bfs1(){
	queue<int> q;
	q.push(1);
	dis[1]=0;
	vis[1]=1;
	while(!q.empty()){
		int xx=q.front();
		q.pop();
		for(int i=h[xx];i;i=e[i].nxt){
			int xxx=e[i].to;
			if(!vis[xxx]){
				q.push(xxx);
				dis[xxx]=dis[xx]+1;
				vis[xxx]=1; 
			}
		}
	}
	return;
}
void bfs2(int x){
	queue<int> q;
	q.push(x);
	for(int i=1;i<=n;i++)
		vis[i]=0;
	disa[x]=0;
	vis[x]=1;
	while(!q.empty()){
		int xx=q.front();
		q.pop();
		for(int i=h[xx];i;i=e[i].nxt){
			int xxx=e[i].to;
			if(!vis[xxx]){
				q.push(xxx);
				disa[xxx]=disa[xx]+1;
				vis[xxx]=1;
			}
		}
	}
	return;
}
int f[100005][21];
int dep[100005];
void dfs(int x,int fa){
    f[x][0]=fa;
    dep[x]=dep[fa]+1;
    for(int i=h[x];i;i=e[i].nxt)
        if(e[i].to!=fa) dfs(e[i].to,x);
    return;
}
void pre(){
    for(int j=1;j<20;j++)
        for(int i=1;i<=n;i++)
            f[i][j]=f[f[i][j-1]][j-1];
    return;
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--)
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;  
    for(int i=19;i>=0;i--)
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}
int bfs4(int x,int y){
	queue<int> q;
	q.push(x);
	for(int i=1;i<=n;i++)
		vis[i]=0;
	disa[x]=0;
	vis[x]=1;
	while(!q.empty()){
		int xx=q.front();
		q.pop();
		for(int i=h[xx];i;i=e[i].nxt){
			int xxx=e[i].to;
			if(!vis[xxx]){
				q.push(xxx);
				disa[xxx]=disa[xx]+1;
				vis[xxx]=1;
				if(xxx==y) return disa[xxx];
			}
		}
	}
	return 0;
}
int main(){
	n=read(),q=read();
	for(int i=1;i<=n-1;i++){
		int u=read(),v=read();
		add(u,v);
		add(v,u); 
	}
	bfs1();
	int far=1;
	for(int i=2;i<=n;i++)
		if(dis[i]>dis[far]) far=i; //1号节点最短路 
	bfs2(far);
	int newfar=1;
	for(int i=2;i<=n;i++) //far号节点最短路,此时newfar为主干线起点 
		if(disa[i]>disa[newfar]) newfar=i;
	bfs2(newfar);
	far=newfar;
	for(int i=1;i<=n;i++) //newfar号节点最短路,此时far为主干线终点
		if(disa[i]>disa[far]) far=i;
	dfs(newfar,0);
	pre();
	for(int i=1;i<=n;i++)
		ans[i]=0x3f3f3f;
	for(int i=1;i<=q;i++){
		int a=read();
		if(ans[a]!=0x3f3f3f) printf("%d\n",ans[i]);
		else{
			ans[a]=bfs4(a,lca(far,a));
			if(ans[a]!=0) ans[a]++;
			printf("%d\n",ans[a]);
		}
	}
	return 0;
}
2021/12/19 12:07
加载中...