3083: 遥远的国度

2024-03-27 04:48

文章标签 国度遥远 3083

本文主要是介绍3083: 遥远的国度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

唔，没初始化 wa了一次…
思路很一眼。
就是说考虑树剖
如果查询点是首都的祖先，那么查询点构成的子树就是整个树除了查询点包含首都的儿子以外所有点。
那么知道一个子树在树剖上是连续一段区间，即现在需要求出包含首都的那棵子树的根，
用类似倍增lca的方法即可。
对于查询点不是首都的祖先的情况，答案直接为查询点这棵子树的答案
搞定
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{char c;int sign = 1;x = 0;do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int N = 1e5+50;
int head[N],to[N<<1],nxt[N<<1],tot;
int n,m,w[N];inline void add(int x,int y)
{to[tot] = y;nxt[tot] = head[x];head[x] = tot++;
}int sz,id[N],idx[N];
struct Segment_tree
{int val[N<<2],lzy[N<<2];void build(int id,int l,int r){if(l == r) return void(val[id] = w[idx[l]]);int mid = l + r >> 1;build(id<<1,l,mid); build(id<<1|1,mid+1,r);val[id] = min(val[id<<1],val[id<<1|1]);}int find(int id,int l,int r,int L,int R){if(l == L && r == R) return val[id];    if(lzy[id]) return lzy[id];int mid = l + r >> 1;if(R <= mid) return find(id<<1,l,mid,L,R);if(L > mid) return find(id<<1|1,mid+1,r,L,R);return min(find(id<<1,l,mid,L,mid),find(id<<1|1,mid+1,r,mid+1,R));}inline void put_down(int id){if(!lzy[id]) return;val[id<<1] = lzy[id<<1] = lzy[id];val[id<<1|1] = lzy[id<<1|1] = lzy[id];lzy[id] = 0;}void update(int id,int l,int r,int L,int R,int w){if(l == L && r == R) return void(val[id]=lzy[id]=w);int mid = l + r >> 1;put_down(id);if(R <= mid) update(id<<1,l,mid,L,R,w);else if(L > mid) update(id<<1|1,mid+1,r,L,R,w);else update(id<<1,l,mid,L,mid,w),update(id<<1|1,mid+1,r,mid+1,R,w);val[id] = min(val[id<<1],val[id<<1|1]);}
}seg;int p[N][21],hson[N],size[N],deep[N],top[N];void dfs1(int x)
{size[x] = 1;for(register int i = head[x];~i;i=nxt[i])if(to[i] != p[x][0]){deep[to[i]] = deep[x] + 1;p[to[i]][0] = x;dfs1(to[i]);size[x] += size[to[i]];if(size[hson[x]] < size[to[i]])hson[x] = to[i];}
}void dfs2(int x,int t)
{top[x] = t; id[x] = ++sz; idx[sz] = x;if(hson[x]) dfs2(hson[x],t);for(register int i = head[x];~i;i=nxt[i])if(to[i]!=hson[x]&&to[i]!=p[x][0])dfs2(to[i],to[i]);
}inline void update(int u,int v,int w)
{while(top[u] != top[v]){if(deep[top[u]] < deep[top[v]]) swap(u,v);seg.update(1,1,n,id[top[u]],id[u],w);u = p[top[u]][0];}if(deep[u] < deep[v]) swap(u,v);seg.update(1,1,n,id[v],id[u],w);
}int q;
inline bool check(int x,int rt)
{if(deep[rt] < deep[x]) return true;repd(i,20,0)if(deep[rt] - (1<<i) > deep[x])rt = p[rt][i];if(p[rt][0] != x) return true;q = rt;return false;
}int rt;
int main()
{memset(head,-1,sizeof head);read(n); read(m);rep(i,2,n){int u,v;read(u); read(v);add(u,v); add(v,u);}rep(i,1,n) read(w[i]);read(rt);dfs1(1);dfs2(1,1);rep(j,1,20)rep(i,1,n)p[i][j] = p[p[i][j-1]][j-1];seg.build(1,1,n);   int op,x;rep(i,1,m){read(op);if(op == 1) read(rt);if(op == 2){int u,v,w;read(u); read(v); read(w);update(u,v,w);}if(op == 3){read(x);if(x == rt) printf("%d\n",seg.val[1]);else if(check(x,rt)){printf("%d\n",seg.find(1,1,n,id[x],id[x]+size[x]-1));}else{printf("%d\n",min(id[q]==1?INT_MAX:seg.find(1,1,n,1,id[q]-1),id[q]+size[q]-1==n?INT_MAX:seg.find(1,1,n,id[q]+size[q],n)));}}}return 0;
}