【题目地址】https://www.spoj.pl/problems/QTREE3/
【题目大意】
给定一棵树，一开始所有点都是白色的。
给定两个操作：
0 x：把点x变色（本来是白色变成黑色，本来是黑色变成白色）
1 x：求从结点1到点x的路径上，第一个黑色的点是哪一个？如果没有，输出-1。
【算法分析】
树链剖分例题(比本文详细)：http://hi.baidu.com/edwardmj/blog/item/2894235220a1be501038c2c9.html
首先显然把结点1当做根变成有根树。
轻重边剖分，然后都于每个重路径建立一棵线段树，然后对于操作0，就把线段树里对应那个点取反即可。
然后对于操作1，就从点x一直向父亲走，遇到重路径就跳到重路径的起始端，并用线段树取最小值，遇到轻边的话就直接走。
【其它】
跑了12s+。。。。果然我写的程序总是比较慢= =
【CODE】
#include
const int INF=1000000000;
struct gtp{int x,y,next,op,inlist;}g[N*2];
struct TT{int l,r,zz;}tr[N*8];
int n,m,e,times,tot,ct,ans;
int ls[N],list[N],fa[N],Size[N],myheavy[N],black[N];
int color[N],cst[N];
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
g[++e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}
void input(){
scanf("%d%d",&n,&m);
for (int i=1,x,y;i
addedge(x,y);
}
}
void predfs(int p){
Size[p]=times++;
for (int t=ls[p];t;t=g[t].next)
if (!fa[p] || t!=g[fa[p]].op){
fa[g[t].y]=t;
predfs(g[t].y);
}
Size[p]=times-Size[p];
}
void dfs(int p){
int mt,mm=-INF;
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && Size[g[t].y]>mm){
mm=Size[g[t].y];
mt=t;
}
if (mm==-INF) return;
myheavy[p]=mt;
list[++tot]=mt;
g[mt].inlist=tot;
dfs(g[mt].y);
for (int t=ls[p];t;t=g[t].next)
if ((!fa[p] || t!=g[fa[p]].op) && t!=mt)
dfs(g[t].y);
}
void draw_color(){
ct=color[1]=cst[1]=1;
for (int i=2;i<=tot;i++){
if (g[list[i-1]].y!=g[list[i]].x) cst[++ct]=i;
color[i]=ct;
}
}
void build(int p,int l,int r){
tr[p].l=l; tr[p].r=r; tr[p].zz=0;
if (l==r) return;
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
}
void change(int p,int x){
if (tr[p].l==tr[p].r){
if (tr[p].zz) tr[p].zz=0;
else tr[p].zz=g[list[x]].x;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (x<=mid) change(p*2,x);
else change(p*2+1,x);
if (tr[p*2].zz) tr[p].zz=tr[p*2].zz;
else tr[p].zz=tr[p*2+1].zz;
}
void Get_zz(int p,int l,int r){
if (l<=tr[p].l && tr[p].r<=r){
if (tr[p].zz) ans=tr[p].zz;
return;
}
int mid=(tr[p].l+tr[p].r)/2;
if (r>mid) Get_zz(p*2+1,l,r);
if (l<=mid) Get_zz(p*2,l,r);
}
void Try(int x){
if (black[x]) ans=x;
if (x==1) return;
if (!g[fa[x]].inlist) Try(g[fa[x]].x);
else{
Get_zz(1,cst[color[g[fa[x]].inlist]],g[fa[x]].inlist);
Try(g[list[cst[color[g[fa[x]].inlist]]]].x);
}
}
void deal(){
for (int op,x,i=1;i<=m;i++){
scanf("%d%d",&op,&x);
if (op==0){
black[x]^=1;
if (myheavy[x]) change(1,g[myheavy[x]].inlist);
}else{
ans=0;
Try(x);
if (ans) printf("%dn",ans);
else printf("-1n");
}
}
}
int main(){
input();
predfs(1);
dfs(1);
draw_color();
build(1,1,tot);
deal();
}