1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; int n,m,head[500007],cent,cnt,h[500007],dep[500007],vis[500007]; int fa[500007],f[2000007],see[500007][3],num[500007]; struct node{ int next,to,w; }edge[1000007]; struct node1{ int next,to,id; }e[3000007];
template<typename type_of_scan> inline void scan(type_of_scan &x){ type_of_scan f=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=f; }
inline void add(int u,int v,int w){ edge[++cent]=(node){head[u],v,w};head[u]=cent; }
inline void add1(int u,int v,int name){ e[++cnt]=(node1){h[u],v,name};h[u]=cnt; }
inline int get(int x){ if(fa[x]==x) return x; return fa[x]=get(fa[x]); }
inline void Tarjan(int u){ vis[u]=1; for(register int i=head[u];i;i=edge[i].next){ int v=edge[i].to; if(vis[v]) continue; dep[v]=dep[u]+edge[i].w; Tarjan(v); fa[v]=u; } for(register int i=h[u];i;i=e[i].next){ int v=e[i].to; if(vis[v]&&!f[e[i].id]){ int zz=get(v),x=e[i].id; f[x]=zz; } } }
inline void work(){ for(register int i=1;i<=3*m;i+=3){ int x=see[i][0],y=see[i][1],z=see[i][2]; int a=f[i],b=f[i+1],c=f[i+2]; if(a==b){ printf("%d %d\n",c,dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c]); }else if(b==c) { printf("%d %d\n",a,dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c]); }else if(a==c) { printf("%d %d\n",b,dep[x]+dep[y]+dep[z]-dep[a]-dep[b]-dep[c]); }
} }
int main(){ scan(n),scan(m); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1,a,b;i<=n-1;i++){ scan(a),scan(b); add(a,b,1),add(b,a,1); } for(register int i=1;i<=3*m;i+=3){ int a,b,c; scan(a),scan(b),scan(c); see[i][0]=a,see[i][1]=b,see[i][2]=c; add1(a,b,i),add1(b,a,i),add1(a,c,i+1); add1(c,a,i+1),add1(c,b,i+2),add1(b,c,i+2); } Tarjan(1); work(); return 0; }
|