# HDU2018多校第四场部分题目

xiaoxiao2021-03-01  8

## C Problems on a Tree（hdu 6334）

#include<bits/stdc++.h> #define N 100010 using namespace std; int T,n,m,f1[N],f2[N],size1[N],size2[N]; int k,la[N],ff[N*2],pre[N],ans,tag,dep[N]; struct node{int a,b,c;}e[N*2]; map<int,int>w[N]; void add(int a,int b,int c) { e[++k]=(node){a,b,c};ff[k]=la[a];la[a]=k; e[++k]=(node){b,a,c};ff[k]=la[b];la[b]=k; } int find1(int x) { if(f1[x]==x)return x; return f1[x]=find1(f1[x]); } int find2(int x) { if(f2[x]==x)return x; return f2[x]=find2(f2[x]); } void merge1(int a,int b) { a=find1(a);b=find1(b); f1[b]=a;size1[a]+=size1[b]; } void merge2(int a,int b) { a=find2(a);b=find2(b); f2[b]=a;size2[a]+=size2[b]; size1[find1(pre[b])]-=size2[b]; size1[find1(pre[a])]+=size2[b]; } void dfs(int x) { dep[x]=dep[pre[x]]+1; for(int a=la[x];a;a=ff[a]) { if(e[a].b==pre[x])continue; pre[e[a].b]=x;size1[x]++;dfs(e[a].b); if(e[a].c<=1)merge1(x,e[a].b); if(e[a].c<=2)merge2(x,e[a].b); } } int main() { int a,b,c,x,y; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m);k=0; memset(la,0,sizeof(la)); memset(ff,0,sizeof(ff)); memset(size1,0,sizeof(size1)); memset(pre,0,sizeof(pre)); for(int i=1;i<=n;i++)f1[i]=i,f2[i]=i,size2[i]=1; for(int i=1;i<n;i++) scanf("%d%d%d",&a,&b,&c),add(a,b,c),w[a][b]=w[b][a]=c; dfs(1); while(m--) { scanf("%d%d%d%d",&a,&b,&x,&y); w[a][b]--;w[b][a]--;tag=0; if(dep[a]>dep[b])swap(a,b); if(w[a][b]==1)merge1(a,b); else if(w[a][b]==2)merge2(a,b); if(find2(x)==find2(y))tag=1; else if(find1(pre[find2(y)])==find1(x))tag=1; else if(find2(y)==find2(pre[find1(x)]))tag=1; ans=size1[find1(x)]+size2[find2(x)]; if(find2(x)!=find2(pre[find1(x)])) ans+=size2[find2(pre[find1(x)])]; printf("%d %d\n",tag,ans); } } return 0; }