请问如何处理边界问题? 能不能载拓扑排序时候寻找至少经过两个关键点的环?
#include<bits/stdc++.h>
using namespace std;
#define maxv 2000000
vector<int> e[4500000],ed[124514];
int in[4500000],cnt,n,u,v,d[124514],m,i,j;
pair<int,int> f[124514][20];
void add(int u,int v)
{
// cerr<<u<<" -> "<<v<<endl;
if(u==v) return;
in[v]++;
e[u].push_back(v);
}
void dfs(int u,int fa)
{
d[u]=d[fa]+1;
f[u][0]={fa,++cnt};
for(i=1;(1<<i)<=d[u];i++)
{
f[u][i]={f[f[u][i-1].first][i-1].first,++cnt};
add(cnt,f[u][i-1].second),add(cnt,f[f[u][i-1].first][i-1].second);
add(f[u][i-1].second+maxv,cnt+maxv),add(f[f[u][i-1].first][i-1].second+maxv,cnt+maxv);
}
for(auto v:ed[u]) if(v!=fa) dfs(v,u);
}
int s[124514],t[124514];
void color(int x,int y,int op,int u)
{
for(int i=18;i>=0;i--) if(d[f[x][i].first]>=d[y]) add(u,f[x][i].second),add(maxv+f[x][i].second,u),x=f[x][i].first;
if(x==y)
{
if(op) add(u,f[x][0].second),add(maxv+f[x][0].second,u);
return;
}
for(int i=18;i>=0;i--) if(f[x][i].first!=f[y][i].first) add(u,f[x][i].second),add(maxv+f[x][i].second,u),x=f[x][i].first,add(u,f[y][i].second),add(maxv+f[y][i].second,u),y=f[y][i].first;
if(op) add(u,f[f[x][0].first][0].second),add(maxv+f[f[x][0].first][0].second,u);
}
void lca(int x,int y,int u)
{
if(x==y||f[x][0].first==y||f[y][0].first==x) return;
if(d[x]<d[y]) swap(x,y);
int xx=x,yy=y;
for(int i=18;i>=0;i--) if(d[f[x][i].first]>=d[y]) x=f[x][i].first;
if(x==y)
color(f[xx][0].first,yy,0,u);
else
color(f[xx][0].first,f[yy][0].first,1,u);
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(i=1;i<n;i++) cin>>u>>v,ed[u].push_back(v),ed[v].push_back(u);
dfs(1,0);
cin>>m;
for(i=1;i<=m;i++)
{
cin>>s[i]>>t[i];
add(2*maxv+i,maxv+f[s[i]][0].second);
add(f[t[i]][0].second,2*maxv+i);
}
for(i=1;i<=m;i++)
{
// add(2*maxv+i,f[s[i]][0].second);
add(f[t[i]][0].second+maxv,2*maxv+i);
lca(s[i],t[i],2*maxv+i);
}
queue<int> q;
for(i=1;i<=cnt;i++)
{
if(in[i]==0) q.push(i);
if(in[i+maxv]==0) q.push(i+maxv);
}
for(i=1;i<=m;i++) if(in[i+2*maxv]==0) q.push(i+2*maxv);
while(!q.empty())
{
int u=q.front();q.pop();
// cerr<<u<<"???"<<endl;
for(auto v:e[u]) if(!--in[v]) q.push(v);
}
bool ans=0;
for(i=1;i<=cnt;i++) ans=((in[i]>0)||(in[i+maxv]>0))?(ans||1):ans, /*cerr<<in[i]<<" "<<in[i+maxv]<<' ',*/e[i].clear(),e[i+maxv].clear(), in[i]=in[i+maxv]=0,e[i].clear(),e[i+maxv].clear();
for(i=1;i<=m;i++) ans=(in[i+2*maxv]>0)?(ans||1):ans,/* cerr<<in[i+2*maxv]<<" ", */e[i+2*maxv].clear(),in[i+2*maxv]=0,e[i+2*maxv].clear();
cnt=0;
puts(ans?"No":"Yes");
for(i=0;i<=n+2;i++) d[i]=0,ed[i].clear(),memset(f[i],0,sizeof(f[i]));
}
return 0;
}