P4281,tarjan全wa,但样例是对。求调玄关!
  • 板块题目总版
  • 楼主wnqnld_llx
  • 当前回复1
  • 已保存回复2
  • 发布时间2025/7/20 14:27
  • 上次更新2025/7/20 17:15:01
查看原帖
P4281,tarjan全wa,但样例是对。求调玄关!
1200401
wnqnld_llx楼主2025/7/20 14:27
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+100;
vector <int> tr[maxn];
int vis[maxn],fa[maxn],first[maxn],second[maxn],third[maxn];
struct node{
	int v,id;
};
vector <node> ask[maxn];
vector <int> ans[maxn];
int n,m;
void init(){
	for(int i=1;i<=n;i++){
		vis[i]=0;
		fa[i]=i;
	}
}
int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
void un(int x,int y){
	fa[find(x)]=find(y);
}
void tarjan(int u){
	vis[u]=1;
	for(int son:tr[u]){
		if(vis[son]) continue;
		tarjan(son);
		un(son,u);
	}
	for(auto ygg:ask[u]){
		int jd=ygg.v,idx=ygg.id;
		if(vis[jd]){
			ans[idx].push_back(find(jd));	
		}
	}
}
int dis[maxn];
void bfs(int u){
	for(int i=1;i<=n;i++) vis[i]=0;
	queue <int> q;
	q.push(u);
	dis[u]=1;
	while(q.size()){
		int now=q.front();
		vis[now]=1;
		q.pop();
		for(auto son:tr[now]){
			if(vis[son]) continue;
			dis[son]=dis[now]+1;
			q.push(son);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		tr[a].push_back(b);
		tr[b].push_back(a);
	}
	bfs(1);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		ask[x].push_back({y,i});
		ask[x].push_back({z,i});
		ask[y].push_back({z,i});
		first[i]=x,second[i]=y,third[i]=z;
	}
	init();
	tarjan(1);
	for(int i=1;i<=m;i++){
		
		int xl=0,yl=0,zl=0,cnt=1;
		for(int pincer:ans[i]){
			if(cnt==1) xl=pincer;
			if(cnt==2) yl=pincer;
			if(cnt==3) zl=pincer;
			cnt++;
		}
		if(xl==yl) cout<<zl<<" ";
		else if(xl==zl) cout<<yl<<" ";
		else if(yl==zl) cout<<xl<<" ";
		cout<<dis[first[i]]+dis[second[i]]+dis[third[i]]-dis[xl]-dis[yl]-dis[zl]<<"\n";
	}
	return 0;
}
2025/7/20 14:27
加载中...