RT,之前一直都是 RE
原代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
const int M = 1000010;
int n,m,s;
struct qes{
int fri,nob;//quest[i]中有 "j,v" 表示第v个问题是求i和j的lca
};
vector<qes> quest[N];
int fa[N];
bool vis[N];
//链式前向星
struct Edge{
int from;
int to;
int next;
} edge[N*2];
int head[N],cnt = 0;
void add(int u,int v){
cnt++;
edge[cnt].from = u;
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
//初始化
void init(){
for(int i = 1; i <= n; i++){
fa[i] = i;
vis[i] = false;
}
}
//主体部分
int findfather(int x){//找父亲
if(fa[x]!=x){fa[x] = findfather(fa[x]);return fa[x];}//找父亲
return x;
}
int answer[M];
void dfs(int id,int fath){
for(int i = head[id]; i; i = edge[i].next){
if(edge[i].to==fath) continue;
dfs(edge[i].to,id);
fa[edge[i].to] = id;
}
for(int i = 0; i <= quest[id].size()-1; i++){
if(vis[quest[id][i].fri]){
answer[quest[id][i].nob] = findfather(quest[id][i].fri);
}
}
vis[id] = true;
}
//主函数
int main(){
cin >> n >> m >> s;
init();
for(int i = 1; i < n; i++){
int u,v;
cin >> u >> v;
add(u,v);
add(v,u);
}
for(int i = 1; i <= m; i++){
int u,v;
cin >> u >> v;
if(u==v) answer[i] = u;
else {
quest[u].push_back((qes){v,i});
quest[v].push_back((qes){u,i});
}
}
dfs(s,s);
for(int i = 1; i <= m; i++) cout << answer[i] << endl;
return 0;
}
但是将 dfs 函数
//之前的
void dfs(int id,int fath){
for(int i = head[id]; i; i = edge[i].next){
if(edge[i].to==fath) continue;
dfs(edge[i].to,id);
fa[edge[i].to] = id;
}
for(int i = 0; i <= quest[id].size()-1; i++){
if(vis[quest[id][i].fri]){
answer[quest[id][i].nob] = findfather(quest[id][i].fri);
}
}
vis[id] = true;
}
改为(改动的行后有 //* 的标记)
//现在的
//vis数组的类型改为 int
void dfs(int id,int fath){
vis[id] = 1;//*
for(int i = head[id]; i; i = edge[i].next){
if(edge[i].to==fath) continue;
dfs(edge[i].to,id);
fa[edge[i].to] = id;
}
for(int i = 0; i < quest[id].size(); i++){
if(vis[quest[id][i].fri]==2){//*
answer[quest[id][i].nob] = findfather(quest[id][i].fri);
}
}
vis[id] = 2;//*
}
后就AC了,之前是全部RE,为什么会这样?