首页 > 代码库 > hust 1016 Black-White Tree
hust 1016 Black-White Tree
题目描述
在图论中，包含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 81 21 32 42 95 97 98 96 81 30 81 61 70 21 90 21 9
样例输出
-18-12-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 0x0f0f0f0fusing 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\n"); else printf("%d\n",b[find(1,n,ans)].x); } } } return 0;}
作者 chensunrise
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。