Windows环境下一点问题没有,洛谷在线 IDE (Linux) 就 RE。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define LL k<<1
#define RR l<<1|1
#define lg log2
const int MAXN=901;
struct edge {
int to,next;
} w[MAXN*2+1];
int h[MAXN+1],cnt=1,d[MAXN+1],prt[MAXN+1],p[MAXN+1][11],n,m,root=1;
set<int>st;
map<int,int>mp;
void AddEdge(int x,int y) {
w[cnt].to=y;
w[cnt].next=h[x];
h[x]=cnt++;
}
void DFS(int x,int deep){
d[x]=d[deep]+1;
p[x][0]=deep;
for(int i=1;(1<<i)<=d[x];i++) {
p[x][i]=p[p[x][i-1]][i-1];
}
for(int i=h[x]; i; i=w[i].next){
if(deep!= w[i].to)DFS(w[i].to,x);
}
}
int LCA(int a,int b) {
int k,i;
if(d[a]<d[b])swap(a,b);
k=lg(d[a]);
for(i=k; i>=0; i--)if(d[a]-(1<<i)>=d[b])a=p[a][i];
if(a==b)return b;
for(i=k; i>=0; i--)
if(p[a][i]!=p[b][i]) {
a=p[a][i];
b=p[b][i];
}
return p[a][0];
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x,y,count;
while(scanf("%lld",&n)){
for(int i=1; i<=n; i++) {
scanf("%lld:(%lld)",&x,&count);
while(count--){
scanf(" %lld",&y);
AddEdge(x,y);
prt[y]=x;
}
}
//寻找root
while(prt[root])root=prt[root];
DFS(root,0);
cin>>m;
for(int i=1; i<=m; i++) {
scanf(" (%lld,%lld)",&x,&y);
int lca=LCA(x,y);//降低时间复杂度
st.insert(lca);
++mp[lca];
}
for(auto kt:st){
printf("%lld:%lld\n",kt,mp[kt]);
}
mp.clear();
st.clear();
cnt=1;
root=1;
for(int i=0;i<=MAXN;i++){
d[i]=0;
prt[i]=0;
h[i]=0;
w[i].to=0;
w[i].next=0;
for(int j=0;j<=10;j++)p[i][j]=-1;
}
for(int i=MAXN+1;i<=2*MAXN;i++){
w[i].to=0;
w[i].next=0;
}
}
return 0;
}
input:
5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5)
(1,4)
(4,2)
(2,3)
(1,3)
(4,3)
5
5:(3) 1 4 2
1:(0)
4:(0)
2:(1) 3
3:(0)
6
(1,5)
(1,4)
(4,2)
(2,3)
(1,3)
(4,3)
output:
2:1
5:5
2:1
5:5