题目大意：给定一棵树，，有两种操作：
1.询问某个点到根的路径上遇到的第一个黑色边的编号
2.将某条路径涂黑
首先将每条边归到它下面的点上
记录每个点到根路径上深度最大的黑点
那么将一个点涂黑就相当于把子树中所有的点的最深黑点取个max
这个用线段树就可以维护
由于一个点最多只会被涂黑一次 因此时间复杂度是O(nlogn)的
现在问题就是如何在每次修改时找到路径上所有白点
这个用并查集就可以搞了
如果一个点被涂黑 那么就把这个点在并查集中向父节点连一条边
然后按照树链剖分那种做法就可以了
总时间复杂度O(nlogn)
加了读入优化之后跑了9888ms
正解难道是线性做法？不明- –
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 1001001using namespace std;struct abcd{int to,next;}table[M<<1];int head[M],tot=1;int n,m;int fa[M],dpt[M],num[M],st[M],ed[M];void Add(int x,int y){table[++tot].to=y;table[tot].next=head[x];head[x]=tot;}void DFS(int x){static int T;int i;st[x]=++T;dpt[x]=dpt[fa[x]]+1;for(i=head[x];i;i=table[i].next)if(table[i].to!=fa[x]){fa[table[i].to]=x;num[table[i].to]=i>>1;DFS(table[i].to);}ed[x]=T;}bool Compare(int x,int y){return dpt[x]<dpt[y];}struct Segtree{Segtree *ls,*rs;int max_dpt_point;Segtree(){ls=rs=0x0;max_dpt_point=0;}void Build_Tree(int x,int y){int mid=x+y>>1;if(x==y) return ;(ls=new Segtree)->Build_Tree(x,mid);(rs=new Segtree)->Build_Tree(mid+1,y);}void Modify(int x,int y,int l,int r,int val){int mid=x+y>>1;if(x==l&&y==r){max_dpt_point=max(max_dpt_point,val,Compare);return ;}if(r<=mid) ls->Modify(x,mid,l,r,val);else if(l>mid) rs->Modify(mid+1,y,l,r,val);else ls->Modify(x,mid,l,mid,val) , rs->Modify(mid+1,y,mid+1,r,val);}int Get_Point(int x,int y,int pos){int mid=x+y>>1;if(x==y) return max_dpt_point;if(pos<=mid)return max(ls->Get_Point(x,mid,pos),max_dpt_point,Compare);elsereturn max(rs->Get_Point(mid+1,y,pos),max_dpt_point,Compare);}}*tree=new Segtree;namespace Union_Find_Set{int belong[M];int Find(int x){if(!belong[x]||belong[x]==x)return belong[x]=x;return belong[x]=Find(belong[x]);}}void Modify(int x,int y){using namespace Union_Find_Set;x=Find(x);y=Find(y);while(x!=y){if(dpt[Find(fa[x])]<dpt[Find(fa[y])])swap(x,y);tree->Modify(1,n,st[x],ed[x],x);belong[x]=fa[x];x=Find(x);}}namespace IStream{#define L (1<<15)char Get_Char(){static char buffer[M],*S,*T;if(S==T){T=(S=buffer)+fread(buffer,1,L,stdin);if(S==T) return EOF;}return *S++;}int Get_Int(){int re=0;char c=0;while(c<'0'||c>'9')c=Get_Char();while(c>='0'&&c<='9')re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();return re;}}int main(){using namespace Union_Find_Set;using namespace IStream;int i,p,x,y;cin>>n>>m;for(i=1;i<n;i++){x=Get_Int();y=Get_Int();Add(x,y);Add(y,x);}DFS(1);tree->Build_Tree(1,n);for(i=1;i<=m;i++){p=Get_Int();if(p==1)x=Get_Int(),printf("%d\n",num[tree->Get_Point(1,n,st[x])]);elsex=Get_Int(),y=Get_Int(),Modify(x,y);}return 0;}
喜欢就喜欢了，心被牵动，无须理由，爱上你是我的自由，
