3083: 遥远的国度
Time Limit: 10 Sec Memory Limit: 1280 MBSubmit: 4375 Solved: 1169
[Submit][Status][Discuss]
Description
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。
问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。
Input
第1行两个整数n m，代表城市个数和操作数。
第2行至第n行，每行两个整数 u v，代表城市u和城市v之间有一条路。
第n+1行，有n个整数，代表所有点的初始防御值。
第n+2行一个整数 id，代表初始的首都为id。
第n+3行至第n+m+2行，首先有一个整数opt，如果opt=1，接下来有一个整数id，代表把首都修改为id；如果opt=2，接下来有三个整数p1 p2 v，代表将p1 p2路径上的所有城市的防御值修改为v；如果opt=3，接下来有一个整数 id，代表询问以城市id为根的子树中的最小防御值。
Output
对于每个opt=3的操作，输出一行代表对应子树的最小点权值。
Sample Input
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
Sample Output
2
3
4
对于20%的数据，n<=1000 m<=1000。
对于另外10%的数据，n<=100000，m<=100000，保证修改为单点修改。
对于另外10%的数据，n<=100000，m<=100000，保证树为一条链。
对于另外10%的数据，n<=100000，m<=100000，没有修改首都的操作。
对于100%的数据，n<=100000，m<=100000，0<所有权值<=2^31。
Source
分析：如果没有换根操作，这就是道树剖+线段树裸题了.
有换根操作，一般并不会真正地去换根,只需要记录新的根在什么位置. 换根对于第二个操作其实是没有影响的. 对于点x的子树，则需要分类讨论. 3种情况：
1. x是root的祖先，那么x往root方向的那个子树的答案不能被统计. 从root往x上跳，令跳到的比x深度大1的点为v,只需要查询
1~L[v] - 1,R[v] + 1 ~ n. dfs序被分成两段.
2.x不是root的祖先，那么x的子树没有变化.
3.x = root,查询整棵树.
大多数换根的题目都不需要真的去换根，分类讨论对其它操作的影响就好了.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int maxn = 200010,inf = 2147483647; int n,m,a[maxn],head[maxn],to[maxn],nextt[maxn],tot = 1,root,id[maxn]; int son[maxn],fa[maxn][20],sizee[maxn],top[maxn],dep[maxn]; int minn[maxn << 1],tag[maxn << 1],newroot,pre[maxn],endd[maxn],dfs_clock; void add(int x,int y) { to[tot] = y; nextt[tot] = head[x]; head[x] = tot++; } void dfs(int u,int faa) { sizee[u] = 0; fa[u][0] = faa; dep[u] = dep[faa] + 1; for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if (v == faa) continue; dfs(v,u); sizee[u] += sizee[v]; if (sizee[son[u]] < sizee[v]) son[u] = v; } } void dfs2(int u,int topp) { top[u] = topp; pre[u] = ++dfs_clock; id[dfs_clock] = u; if (son[u]) dfs2(son[u],topp); for (int i = head[u]; i; i = nextt[i]) { int v = to[i]; if(v == fa[u][0] || v == son[u]) continue; dfs2(v,v); } endd[u] = dfs_clock; } void pushup(int o) { minn[o] = min(minn[o * 2],minn[o * 2 + 1]); } void pushdown(int o) { if (tag[o]) { tag[o * 2] = tag[o]; tag[o * 2 + 1] = tag[o]; minn[o * 2] = tag[o]; minn[o * 2 + 1] = tag[o]; tag[o] = 0; } } void build(int o,int l,int r) { if (l == r) { minn[o] = a[id[l]]; return; } int mid = (l + r) >> 1; build(o * 2,l,mid); build(o * 2 + 1,mid + 1,r); pushup(o); } void update(int o,int l,int r,int x,int y,int v) { if (x <= l && r <= y) { minn[o] = v; tag[o] = v; return; } pushdown(o); int mid = (l + r) >> 1; if (x <= mid) update(o * 2,l,mid,x,y,v); if (y > mid) update(o * 2 + 1,mid + 1,r,x,y,v); pushup(o); } int lca(int x,int y) { if (dep[x] < dep[y]) swap(x,y); for (int i = 19; i >= 0; i--) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if (x == y) return x; for (int i = 19; i >= 0; i--) if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } return fa[x][0]; } void Update(int x,int y,int d) { while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x,y); update(1,1,n,pre[top[x]],pre[x],d); x = fa[top[x]][0]; } if (dep[x] < dep[y]) swap(x,y); update(1,1,n,pre[y],pre[x],d); } int query(int o,int l,int r,int x,int y) { if (x <= l && r <= y) return minn[o]; pushdown(o); int mid = (l + r) >> 1,res = inf; if (x <= mid) res = min(res,query(o * 2,l,mid,x,y)); if (y > mid) res = min(res,query(o * 2 + 1,mid + 1,r,x,y)); return res; } int jump(int x,int d) { for (int i = 19; i >= 0; i--) if (dep[fa[x][i]] >= d) x = fa[x][i]; return x; } int Query(int x) { if (x == root) return query(1,1,n,1,n); int p = lca(x,root); if (x != p) return query(1,1,n,pre[x],endd[x]); int v = jump(root,dep[x] + 1); return min(query(1,1,n,endd[v] + 1,n),query(1,1,n,1,pre[v] - 1)); } int main() { scanf("%d%d",&n,&m); for (int i = 1; i < n; i++) { int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } for (int i = 1; i <= n; i++) scanf("%d",&a[i]); scanf("%d",&root); dfs(root,0); for (int j = 1; j <= 19; j++) for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1]; dfs2(root,root); build(1,1,n); for (int i = 1; i <= m; i++) { int opt; scanf("%d",&opt); if (opt == 1) { int t; scanf("%d",&t); root = t; } if (opt == 2) { int x,y,d; scanf("%d%d%d",&x,&y,&d); Update(x,y,d); } if (opt == 3) { int t; scanf("%d",&t); printf("%d ",Query(t)); } } return 0; }