题目描述 http://acm.hdu.edu.cn/showproblem.php?pid=6334
题解 打比赛的时候想歪了，一直往动态点分治的方向想了，不知道要怎么修改。 对于这个题，我们维护两种并查集，一种只连所有1的边，记为1集合，一种连所有1和2的边，记为2集合。 对于每次询问，第一问只要考虑x点的1集合和y点的2集合是否相连，或者反过来，或者x点和y点爱同一个2集合。 第二问，题目要求以x点为终点的起点数，就是x点所在的2集合的点数，记为size2[x]，再加上它所相邻的点的1集合的点数，记为size1[x]。出于处理方便，size1[x]只记录叶子节点的，父亲节点的查询的时候再找一下就好了。 对于修改操作，如果是3改2，那么就把这两个点在2集合连起来，把size1和size2对应的改一下。 如果是2改1，那么就把两个1集合合并一下，也修改一下它父亲的size2就好了。
代码
#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; }