【題目描述】
SPOJ - QTREE3Query on a tree again!

【題目分析】
題目要求是輸出從$1$到$x$的路徑上遇到的第一個黑色的點。我們可以用樹鏈剖分（不了解的同學請出門左拐，詳見樹鏈剖分入門）
我們用線段樹維護每個區間第一次遇到黑點的位置，這樣訪問出的點同樣是從1開始路徑上的第一個點。因為我們總是從根節點1開始，我們在訪問的時候從后往前每次訪問重鏈時在線段樹上都是一段連續的區間，因此在映射數組的位置越靠前則在路徑上越靠前
【AC代碼】

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>using namespace std;const int MAXN=100005;
vector<int>g[MAXN];
int fa[MAXN],A[MAXN],color[MAXN],pos[MAXN],siz[MAXN],son[MAXN],h[MAXN],top[MAXN],re[MAXN];
int cnt=0,n,m;
int Min[MAXN<<2];void dfs1(int u,int f)
{int i,v;siz[u]=1;son[u]=0;fa[u]=f;h[u]=h[f]+1;for(i=0;i<g[u].size();i++){v=g[u][i];if(v!=f){dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v]) son[u]=v;}}
}
void dfs2(int u,int f,int k)
{int i,v;top[u]=k;pos[u]=++cnt;re[cnt]=u;//A[cnt]=INT_MAX;if(son[u]) dfs2(son[u],u,k);for(i=0;i<g[u].size();i++){v=g[u][i];if(v!=f&&v!=son[u]) dfs2(v,u,v);}
}void build(int k,int l,int r)
{if(l==r){Min[k]=INT_MAX;return; }int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);Min[k]=min(Min[k<<1],Min[k<<1|1]);
}void update(int k,int l,int r,int x,int color)
{if(l==r){if(color==1)Min[k]=l;elseMin[k]=INT_MAX;return;}int mid=(l+r)/2;if(x<=mid) update(k<<1,l,mid,x,color);else update(k<<1|1,mid+1,r,x,color);Min[k]=min(Min[k<<1],Min[k<<1|1]);
}int QueryMin(int k,int l,int r,int L,int R)
{if(L<=l && r<=R) return Min[k];int mid=(l+r)/2;int ret=INT_MAX;if(L<=mid) ret=min(ret,QueryMin(k<<1,l,mid,L,R));if(R>mid) ret=min(ret,QueryMin(k<<1|1,mid+1,r,L,R));return ret;
}int FindMin(int u)
{int ans=INT_MAX;while(top[u]!=1){ans=min(ans,QueryMin(1,1,n,pos[top[u]],pos[u]));u=fa[top[u]];}ans=min(ans,QueryMin(1,1,n,1,pos[u]));return ans;
}int main()
{int a,b,r,l,mid,ans;memset(A,0,sizeof(A));memset(color,0,sizeof(color));scanf("%d%d",&n,&m);for(int i=1;i<n;i++){scanf("%d%d",&a,&b);g[a].push_back(b);g[b].push_back(a);}dfs1(1,0);dfs2(1,0,1);build(1,1,n);while(m--){scanf("%d%d",&a,&b);if(a==0) {color[b]=!color[b];update(1,1,n,pos[b],color[b]);}else{ans=FindMin(b);if(ans==INT_MAX){printf("-1\n");}else{printf("%d\n",re[ans]);	//維護的是在映射數組上的下標，應該用一個數組保存從下標到節點的映射}}}return 0;
}