维护1边的联通块和2边的联通块，合并的时候直接启发式合并。
cdqz的大爷好强啊。
#include<bits/stdc++.h> #define lson (o<<1) #define rson (o<<1|1) #define fi first #define sc second #define dbg(x) cout<<#x<<" = "<<(x)<<endl; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; using namespace std; const double pi=acos(-1); const double eps=1e-6; inline int lowbit(int x){return x&(-x);} inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } template<typename T> inline T max(T x,T y,T z){return max(max(x,y),z);} template<typename T> inline T min(T x,T y,T z){return min(min(x,y),z);} template<typename T> inline T sqr(T x){return x*x;} template<typename T> inline void checkmax(T &x,T y){x=max(x,y);} template<typename T> inline void checkmin(T &x,T y){x=min(x,y);} template<typename T> inline void read(T &x){ x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f; } template<typename A,typename B,typename C> inline A fpow(A x,B p,C yql){ A ans=1; for(;p;p>>=1,x=1LL*x*x%yql)if(p&1)ans=1LL*x*ans%yql; return ans; } struct FastIO{ static const int S=1310720; int wpos;char wbuf[S]; FastIO():wpos(0) {} inline int xchar(){ static char buf[S]; static int len=0,pos=0; if(pos==len)pos=0,len=fread(buf,1,S,stdin); if(pos==len)return -1; return buf[pos++]; } inline int read(){ int c=xchar(),x=0; while(c<=32&&~c)c=xchar(); if(c==-1)return -1; for(;'0'<=c&&c<='9';c=xchar())x=x*10+c-'0'; return x; } }io; //#define read io.read const int N=200010; int add[N],tag2[N],fa1[N],fa2[N],size1[N],size2[N],fa[N],d[N]; int n,m; vector<int> G[N]; inline int find(int *fa,int x){return x==fa[x]?x:fa[x]=find(fa,fa[x]);} inline void merge2(int x,int y){ int xx=find(fa1,x),yy=find(fa1,y); if(d[xx]<d[yy])swap(xx,yy); add[yy]-=size2[xx];yy=find(fa2,yy); fa2[xx]=yy;size2[yy]+=size2[xx]; add[find(fa1,fa[yy])]+=size2[xx]; } inline void merge1(int x,int y){ int xx=find(fa1,x),yy=find(fa1,y); if(d[xx]<d[yy])swap(xx,yy); fa1[xx]=yy;size1[yy]+=size1[xx]; add[yy]+=add[xx]; } inline void dfs(int u){ d[u]=d[fa[u]]+1; add[u]=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(v==fa[u])continue; fa[v]=u;dfs(v);add[u]++; } } vector<pair<int,int> >p1,p2; inline void clear(){ memset(add,0,sizeof(add)); for(int i=1;i<=n;i++){ fa1[i]=i;fa2[i]=i;size1[i]=1;size2[i]=1;G[i].clear(); } p1.clear();p2.clear(); } inline void work(){ for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); G[u].push_back(v);G[v].push_back(u); if(w==1){ p1.push_back(make_pair(u,v)); //merge2(u,v);merge1(u,v); } else if(w==2)p2.push_back(make_pair(u,v)); } dfs(1); for(int i=0;i<p1.size();i++){ pair<int,int> p=p1[i]; merge2(p.fi,p.sc);merge1(p.fi,p.sc); } for(int i=0;i<p2.size();i++){ pair<int,int> p=p2[i]; merge2(p.fi,p.sc); } while(m--){ int u=read(),v=read(),t=read(),s=read(); u=find(fa1,u);v=find(fa1,v); if(u!=v){ if(find(fa2,u)==find(fa2,v))merge1(u,v); else merge2(u,v); } s=find(fa1,s);t=find(fa1,t);int flag=0; if(find(fa2,s)==find(fa2,t))printf("1 "),flag=1; else{ if(d[find(fa2,s)]>d[find(fa2,t)]){ if(find(fa1,fa[find(fa2,s)])==t)printf("1 "),flag=1; } else if((t==find(fa2,t)&&find(fa2,fa[t])==find(fa2,s)))printf("1 "),flag=1; } if(!flag)printf("0 "); printf("%d ",size2[find(fa2,t)]+add[t]+(t==find(fa2,t)?size2[find(fa2,fa[t])]:0)); } } int main(){ int T=read(); while(T--){ n=read();m=read(); clear(); work(); } }