题目描述
在图论中，包含n个结点（结点编号为1~n）、n-1条边的无向连通图被称为树。 在树中，任意一对结点间的简单路径总是惟一的。 你拥有一棵白色的树——所有节点都是白色的。接下来，你需要处理c条指令： 修改指令(0 v)：改变一个给定结点的颜色（白变黑，黑变白）； 查询指令(1 v)：询问从结点1到一个给定结点所经过的第一个黑色结点编号（假设沿着简单路径走）。 注意，在查询指令中，必须从结点1而不是结点v出发。如果结点1本身就是黑色，查询指令应该返回1。
输入
第一行包含两个正整数n, c，即结点数和指令条数，n和c都不大于1,000,000. 以下n-1行，每行两个正整数(ui, vi) (1 <= ui < vi <= n)，表示结点ui到vi之间有一条无向边。 以下c行，每行两个整数(c, v)。当c=0时表示修改指令，其中v代表被修改的结点编号；c=1时表示查询指令。 你的程序需要输出结点1到结点v之间路径的第一个黑色结点编号。 在第一条指令执行前，所有结点都是白色的。
输出
对于每个查询操作(c=1的操作)，输出一行，包含一个整数，即第一个黑色结点的编号。如果不存在黑色结点，输出-1。样例输入
9 8 1 2 1 3 2 4 2 9 5 9 7 9 8 9 6 8 1 3 0 8 1 6 1 7 0 2 1 9 0 2 1 9
样例输出
-1 8 -1 2 -1
百度之星2008的题目，真的是一道超级好题啊，一开始怎么都不知道方法，后来看了某人的方法说进行路径压缩，就是有些链可以压缩一下，这样来求，于是写了一个，不过还是超时了，后来再无意中看到一份牛X的解法
“以1为根建树，则题目问的就是每个点到根的路径中深度最小的黑色点。先dfs一次纪录每个点的入栈时间in[i]和出栈时间out[i]。注意dfs要用回溯法，要不会堆栈溢出，因为n最大为10^6。
根据v的祖先u有 in[u] < in[v] && out[v] < out[u] 的性质，先将所有节点按in[]序，然后用一个线段树维护按in[]排序后的out[] * color值（color=0表示白色,1表示黑色）。
对于题目的每个询问v。等价于在区间[1, rank[v]]里查找一个out[i]*color的最大值。rank[v]表示v按in排序后的位置)，如果满足out[v] <= x则x对应的节点编号为答案(越大越靠近根,乘color用于排除白色节点的影响)。”
多么牛的解法啊，首先这个题如果知道这么做了，那就不是难题了，主要的是把dfs的递归转化成非递归，方法就是自己定义一个栈来模拟递归过程，其次的二分，线段树之类的就不用我说了，直接写就可以了，由于网上好像没有代码吧！贴一下我的代码，8000msAC的，其实还可以在优化，不过已经够了
#include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 0x0f0f0f0f using namespace std; const int maxn=1000000+10; struct node { int col,in,out,id; }a[maxn]; struct node2 { int x,date; }b[maxn]; struct node1 { int L,R,mmax; }tree[maxn*4]; vector<int>G[maxn]; bool vis[maxn]; bool cmp(node2 x,node2 y) { return x.date<y.date; } void dfs(int n) { stack<int>S; int dfs_clock=1,ID=1; a[1].col=0; a[1].in=1; vis[1]=true; a[1].id=1; S.push(1); while(!S.empty()) { int u=S.top(); bool cut=false; for (int i=0;i<G[u].size();i++) { int v=G[u][i]; if (!vis[v]) { cut=true; dfs_clock++; ID++; vis[v]=1; a[v].col=0; a[v].in=dfs_clock;a[v].id=ID; S.push(v); break; } } if (!cut) { dfs_clock++; S.pop(); a[u].out=dfs_clock; } } } void build(int c,int x,int y) { tree[c].L=x; tree[c].R=y; tree[c].mmax=0; if (x==y) return; int mid=x+(y-x)/2; build(c*2,x,mid); build(c*2+1,mid+1,y); } void update(int c,int x,int v) { if (tree[c].L==x && tree[c].R==x) { tree[c].mmax=v; return; } int mid=tree[c].L+(tree[c].R-tree[c].L)/2; if (x<=mid) update(c*2,x,v); else update(c*2+1,x,v); tree[c].mmax=max(tree[c*2].mmax,tree[c*2+1].mmax); } int get_max(int c,int x,int y) { if (tree[c].L==x && tree[c].R==y) return tree[c].mmax; int mid=tree[c].L+(tree[c].R-tree[c].L)/2; if (y<=mid) return get_max(c*2,x,y); else if(x>mid) return get_max(c*2+1,x,y); else { return max(get_max(c*2,x,mid),get_max(c*2+1,mid+1,y)); } } void init(int n) { for (int i=0;i<=n;i++) { G[i].clear(); vis[i]=0; } } int find(int x,int y,int v) { while(x<y) { int m=x+(y-x)/2; if (b[m].date>=v) y=m; else x=m+1; } return x; } int main() { int n,m,x,y; while (scanf("%d%d",&n,&m)!=EOF) { init(n); build(1,1,n); for (int i=1;i<n;i++) { scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } dfs(1); for (int i=1;i<=n;i++) { b[i].x=i; b[i].date=a[i].out; } sort(b+1,b+n+1,cmp); while(m--) { scanf("%d%d",&x,&y); if (x==0) { a[y].col=a[y].col^1; int v=a[y].col*a[y].out; update(1,a[y].id,v); } else { int ans=get_max(1,1,a[y].id); if (ans==0 || ans<a[y].in) printf("-1 "); else printf("%d ",b[find(1,n,ans)].x); } } } return 0; }
作者 chensunrise