struct seg { int l, r; int flag; int id; }s[N]; int split(int x, int y) { int cnt = 0; int flag=0; int fx = top[x], fy = top[y]; while (fx != fy) { if (dep[fx] < dep[fy]) { swap(fx, fy); swap(x, y); flag=!flag; } s[cnt].flag=flag,s[cnt].id=cnt; s[cnt].l = dfn[fx],s[cnt++].r = dfn[x]; x = fa[fx]; fx = top[x]; } if (dfn[x] > dfn[y]){ swap(x, y); flag=!flag; } s[cnt].flag=!flag,s[cnt].id=cnt; s[cnt].l = dfn[x], s[cnt++].r = dfn[y]; return cnt; } bool cmp(seg a,seg b){ if(a.flag==b.flag){ if(a.flag){ return a.id>b.id; } else{ return a.id<b.id; } } else return a.flag<b.flag; }