http://www.spoj.com/problems/QTREE3/
时间限制:2s 代码长度限制:50000B 内存限制：1536MB
【题目描述】
给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白
有两种操作：
0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）
1 v : 询问1到v的路径上的第一个黑点，若无，输出-1
总共有12组数据。
1/3 的数据, N=5000, Q=400000.
1/3 的数据, N=10000, Q=300000.
1/3 的数据，N=100000, Q=100000.
【输入格式】
单组数据的。
第一行 N and Q.表示N个点和Q个操作
下来N-1条无向边
下来 Q行，每行一个操作"0 i" 或者"1 v" (1 ≤ i, v ≤ N).
【输出格式】
遇到 "1 v"操作的时候，输出结果。
这题就是树链剖分，线段树维护当前区间最左边的黑点的编号。因为是单点修改，所以根本不用lazy，也不用记录点的颜色（看它所维护的最左边的点这个值是否为0）。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int N=;
struct trnode{
int lc,rc,l,r,c,d,lazy;
}t[*N];
struct node{
int x,y,next;
}a[*N];
int n,m,tl,z,len;
int first[N],tot[N],son[N],fa[N],dep[N],ys[N],yss[N],top[N]; void ins(int x,int y)
{
len++;
a[len].x=x;a[len].y=y;
a[len].next=first[x];first[x]=len;
} int maxx(int x,int y){return x>y ? x:y;}
int minn(int x,int y){return x<y ? x:y;} int build_tree(int l,int r)
{
int x=++tl;
t[x].l=l;t[x].r=r;
t[x].c=t[x].d=t[x].lazy=;
t[x].lc=t[x].rc=;
if(l<r)
{
int mid=(l+r)>>;
t[x].lc=build_tree(l,mid);
t[x].rc=build_tree(mid+,r);
}
return x;
} void change(int x,int p)
{
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;
if(t[x].l==t[x].r)
{
if(t[x].d==) t[x].d=t[x].l;
else t[x].d=;
return;
}
if(p<=mid) change(lc,p);
else change(rc,p);
if(t[lc].d) t[x].d=t[lc].d;
else if(t[rc].d) t[x].d=t[rc].d;
else t[x].d=;
} int query(int x,int l,int r)
{
if(t[x].l==l && t[x].r==r) return t[x].d;
int lc=t[x].lc,rc=t[x].rc,mid=(t[x].l+t[x].r)>>;
if(r<=mid) return query(lc,l,r);
else if(l>mid) return query(rc,l,r);
else
{
int t1=query(lc,l,mid);
if(t1) return t1;
int t2=query(rc,mid+,r);
if(t2) return t2;
return ;
}
} void dfs1(int x)
{
tot[x]=;son[x]=;
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa[x]) continue;
fa[y]=x;
dep[y]=dep[x]+;
dfs1(y);
if(tot[son[x]]<tot[y]) son[x]=y;
tot[x]+=tot[y];
}
} void dfs2(int x,int tp)
{
ys[x]=++z;yss[z]=x;top[x]=tp;
if(son[x]) dfs2(son[x],tp);
for(int i=first[x];i;i=a[i].next)
{
int y=a[i].y;
if(y==fa[x] || y==son[x]) continue;
dfs2(y,y);
}
} int solve(int y)
{
int ty=top[y],ans=-;
while(ty!=)
{
int t=query(,ys[ty],ys[y]);
if(t) ans=yss[t];
y=fa[ty];ty=top[y];
}
int t;
if(y==) t=query(,,);
else t=query(,,ys[y]);
if(t) ans=yss[t];
return ans;
} int main()
{
freopen("a.in","r",stdin);
// freopen("me.out","w",stdout);
scanf("%d%d",&n,&m);
tl=;len=;z=;
memset(first,,sizeof(first));
for(int i=;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
ins(x,y),ins(y,x);
}
build_tree(,n);
fa[]=;dep[]=;dfs1();
dfs2(,);
for(int i=;i<=m;i++)
{
int tmp,x;
scanf("%d%d",&tmp,&x);
if(!tmp) change(,ys[x]);
else
{
int ans=solve(x);
if(ans) printf("%d\n",ans);
else printf("-1\n");
}
}
return ;
}