测试点 1 下载下来了能过但是交上去全都RE掉,显示“Aborted / IOT trap”
#include<bits/stdc++.h>
using namespace std;
template <class T>
struct Stack{
vector<T> s;
void push(T x){s.push_back(x);}
T top(){return *(s.end()-1);}
T second(){return *(s.end()-2);}
T pop(){s.pop_back();}
bool empty(){return s.empty();}
int size(){return s.size();}
// T val(int x){return s[x];}
};
const int N=100005;
vector<int> e[N],id[N];
int dfn[N],dep[N],f[N][20],cnt;
void init(int u,int fa){
dfn[u]=++cnt; dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;i<20;i++)
f[u][i]=f[f[u][i-1]][i-1];
// printf("%d %d %d\n",u,f[u][0],f[u][1]);
for(int v:e[u]){
if(v==fa) continue;
init(v,u);
}
}
int lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
for(int i=19;i>=0;i--)
if((dep[a]-dep[b])&(1<<i))
a=f[a][i];
if(a==b) return a;
for(int i=19;i>=0;i--)
if(f[a][i]!=f[b][i])
a=f[a][i],b=f[b][i];
return f[a][0];
}
bool cmp(int a,int b){return dfn[a]<dfn[b];}
int n,m,k,u,v,r,a[N];
int val[N];
void virtualtree(){
// printf("HERE\n");
sort(a+1,a+r+1,cmp);
Stack<int> st;
st.push(0);
st.push(0);
st.push(a[1]);
for(int i=2;i<=r;i++){
// printf("HERE\n");
int x=lca(st.top(),a[i]);
// printf("%d %d %d\n",st.top(),a[i],x);
if(x==st.top()){
st.push(a[i]);
continue;
}
while(dep[st.second()]>dep[x]){
val[st.top()]++;
val[st.second()]--;
// printf("%d++ %d--\n",st.top(),st.second());
st.pop();
}
val[st.top()]++;
val[x]--;
// printf("%d++ %d--\n",st.top(),x);
st.pop();
if(st.top()!=x)
st.push(x);
st.push(a[i]);
}
while(st.size()>3){
val[st.top()]++;
val[st.second()]--;
// printf("%d++ %d--\n",st.top(),st.second());
st.pop();
}
}
int anslis[N],len;
void dfs(int u,int fa){
vector<int>::iterator it=id[u].begin();
for(int v:e[u]){
if(v==fa){
it++;
continue;
}
dfs(v,u);
val[u]+=val[v];
if(val[v]>=k) anslis[++len]=*it;
// printf("edge %d->%d (%d): %d\n",u,v,*it,val[v]);
it++;
}
}
int main(){
// freopen("P6572_1.in","r",stdin);
// freopen("myoutput.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
e[u].push_back(v);
id[u].push_back(i);
e[v].push_back(u);
id[v].push_back(i);
}
init(1,0);
for(int i=1;i<=m;i++){
scanf("%d",&r);
for(int j=1;j<=r;j++)
scanf("%d",&a[j]);
virtualtree();
}
dfs(1,0);
printf("%d\n",len);
sort(anslis+1,anslis+len+1);
for(int i=1;i<=len;i++)
printf("%d ",anslis[i]);
}