链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解:http://medalplus.com/?p=1685
题解
- 强制在线做法 O(nlogn)
考虑每一次标记点:只会影响其子树中的点
所以使用DFS序+线段树就可以辣! -
离线做法 O(nlogn)
考虑将每一次标记的时间记录到点上
然后使用倍增LCA的思想向上倍增 -
离线做法 O(nα(n))
考虑离线之后进行逆序操作
这样的话,操作就变成了删除标记
这个可以形象地想成:打通了向上走地道路
于是使用并查集即可
ps:和BZOJ_3319是一毛一样的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; int head[N],to[N],nxt[N],anc[N],fa[N]; int n,m,tot,opt[N],tag[N],vout[N]; char pat[10]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int find(int w) { int f=fa[w],tmp; while (fa[f] != f) f = fa[f]; while (w != f) tmp=fa[w], fa[w]=f, w=tmp; return f; } inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; } void DFS(int w, int last) { if (tag[w]) last = fa[w] = w; else fa[w] = last; for (int i=head[w];i;i=nxt[i]) { anc[to[i]] = w; DFS(to[i],last); } } int main(){ n = read(); m = read(); for (int i=1,u,v;i<n;i++) { u = read(); v = read(); Add_Edge(u,v); } for (int i=1;i<=m;i++) { scanf("%s",pat+1); opt[i] = read(); if (pat[1] == 'C') tag[opt[i]]++; else opt[i] *= -1; } tag[1]++; DFS(1,1); for (int i=m;i;i--) { if (opt[i] > 0) { if (!(--tag[opt[i]])) { fa[opt[i]] = anc[opt[i]]; } } else { vout[++tot] = find(-opt[i]); } } while (tot) printf("%d\n",vout[tot--]); return 0; }
I got what you intend,saved to bookmarks, very nice web site.
you are really a good webmaster. The website loading speed is amazing. It seems that you’re doing any unique trick. In addition, The contents are masterwork. you’ve done a fantastic job on this topic!