3083: 遥远的国度
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 797 Solved: 181
[Submit][Status]
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
3 7
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
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
1
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。
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。
思路来自hja，劲爆的读入优化来自zhonghaoxi，基本自己没想什么，还Wa了很久。
主要就是树链剖分。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cctype> using namespace std; #define INF 0x3f3f3f3f #define MAXN 110000 #define lch (now<<1) #define rch (now<<1^1) typedef long long qword; #ifdef unix #define LL "%d" #else #define LL "%I64d" #endif const int BUF_SIZE = 30; char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1; #define PTR_NEXT() { buf_s ++; if (buf_s == buf_t) { buf_s = buf; buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); } } #define readint(_n_) { while (*buf_s != '-' && !isdigit(*buf_s)) PTR_NEXT(); bool register _nega_ = false; if (*buf_s == '-') { _nega_ = true; PTR_NEXT(); } int register _x_ = 0; while (isdigit(*buf_s)) { _x_ = _x_ * 10 + *buf_s - '0'; PTR_NEXT(); } if (_nega_) _x_ = -_x_; (_n_) = (_x_); } int n,m; int val_t[MAXN]; //segment_tree{{{ struct segt { int l,r,val; int tag; }tree[MAXN*4]; int ptr[MAXN]; void down(int now) { if (tree[now].tag!=INF) { tree[lch].val=tree[rch].val=tree[lch].tag=tree[rch].tag=tree[now].tag; tree[now].tag=INF; } } void update(int now) { if (tree[now].l==tree[now].r)return ; tree[now].val=min(tree[lch].val,tree[rch].val); } void build_tree(int now,int l,int r) { tree[now].l=l; tree[now].r=r; tree[now].tag=INF; if (l==r){ ptr[l]=now; tree[now].val=val_t[l]; return; } int mid=(l+r)>>1; build_tree(lch,l,mid); build_tree(rch,mid+1,r); update(now); } /* void set_val(int pos,int val) { pos=ptr[pos]; tree[pos].val=val; while (pos) { update(pos); pos>>=1; } }*/ void set_seg(int now,int l,int r,int val) { down(now); if (tree[now].l==l&&tree[now].r==r) { tree[now].val=val; tree[now].tag=val; return ; } int mid=(tree[now].l+tree[now].r)>>1; if (r<=mid) { set_seg(lch,l,r,val); update(now); return ; } if (mid<l) { set_seg(rch,l,r,val); update(now); return ; } set_seg(lch,l,mid,val); set_seg(rch,mid+1,r,val); update(now); } int query_min(int now,int l,int r) { down(now); if (tree[now].l==l&&tree[now].r==r) { return tree[now].val; } int mid; mid=(tree[now].l+tree[now].r)>>1; if (r<=mid) { return query_min(lch,l,r); } if (mid<l) { return query_min(rch,l,r); } return min(query_min(lch,l,mid),query_min(rch,mid+1,r)); } //}}} struct Edge { int np; Edge *next; }E[MAXN*2],*V[MAXN]; int root,tope=-1; void addedge(int x,int y) { E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope]; } int dfn[MAXN],l[MAXN],fa[MAXN],inp[MAXN],oup[MAXN]; int depth[MAXN]; int cnt=0; int siz_s[MAXN],son[MAXN]; int siz_t[MAXN]; int top[MAXN]; int dfs(int now,int dep) { Edge *ne; int t; siz_s[now]=0; siz_t[now]=1; depth[now]=dep; for (ne=V[now];ne;ne=ne->next) { if (fa[now]!=ne->np) { fa[ne->np]=now; t=dfs(ne->np,dep+1); siz_t[now]+=t; if (t>siz_s[now]) { siz_s[now]=t; son[now]=ne->np; } } } return siz_t[now]; } void dfs2(int now,int tp) { Edge *ne; dfn[now]=++cnt; inp[now]=cnt; l[cnt]=val_t[now]; top[now]=tp; if (son[now])dfs2(son[now],tp); for (ne=V[now];ne;ne=ne->next) { if (fa[now]!=ne->np&&son[now]!=ne->np) { dfs2(ne->np,ne->np); } } oup[now]=cnt; } int jump[20][MAXN],topj; void init_lca() { int i,j; for (i=1;i<=n;i++)jump[0][i]=fa[i]; bool flag=true; for (i=1;i<20&&flag;i++) { flag=false; topj=i; for (j=1;j<=n;j++) { jump[i][j]=jump[i-1][jump[i-1][j]]; if (jump[i][j]!=root)flag=true; } } } void swim(int &x,int l) { int i=0; while (l) { if (l&1)x=jump[i][x]; i++; l>>=1; } } int lca(int x,int y) { if (depth[x]<depth[y]) { swim(y,depth[y]-depth[x]); } if (depth[x]>depth[y]) { swim(x,depth[x]-depth[y]); } if (x==y)return x; for (int i=topj;i>=0;i--) { if (jump[i][x]!=jump[i][y]) { x=jump[i][x]; y=jump[i][y]; } } return fa[x]; } int id; int main() { freopen("input.txt","r",stdin); //freopen("output2.txt","w",stdout); //scanf("%d%d",&n,&m); readint(n); readint(m); int i,j,k,x,y,z; int a; for (i=1;i<n;i++) { //scanf("%d%d",&x,&y); readint(x); readint(y); addedge(x,y); addedge(y,x); } root=1; fa[root]=root; dfs(root,1); dfs2(root,root); init_lca(); for (i=1;i<=n;i++) { readint(x); //scanf("%d",&x); val_t[dfn[i]]=x; } build_tree(1,1,cnt); readint(id); //scanf("%d",&id); int opt,ans; //cout<<"a"; for (i=0;i<m;i++) { //scanf("%d",&opt); readint(opt); if (opt==1) { //scanf("%d",&id); readint(id); } if (opt==2) { //scanf("%d%d%d",&x,&y,&z); readint(x); readint(y); readint(z); while (top[x]!=top[y]) { if (depth[top[x]]<depth[top[y]])swap(x,y); set_seg(1,dfn[top[x]],dfn[x],z); x=fa[top[x]]; } if (dfn[x]<dfn[y]) { set_seg(1,dfn[x],dfn[y],z); }else { set_seg(1,dfn[y],dfn[x],z); } } if (opt==3) { //scanf("%d",&x); readint(x); if (x==id) { ans=query_min(1,1,n); printf("%d ",ans); continue; } if (x==root) { LABEL2: y=id; /* for (j=topj;j>=0;j--) { if (jump[j][y]!=x) { y=jump[j][y]; } }*/ swim(y,depth[y]-depth[x]-1); ans=INF; if (inp[y]!=1)ans=query_min(1,1,inp[y]-1); if (oup[y]!=n)ans=min(ans,query_min(1,oup[y]+1,n)); printf("%d ",ans); continue; } if (depth[x]>=depth[id]) { LABEL1: ans=query_min(1,inp[x],oup[x]); printf("%d ",ans); continue; } if (lca(x,id)==x) { /* ans=INF; ans=query_min(1,1,inp[x]); if (oup[x]!=n)ans=min(ans,query_min(1,oup[x]+1,n)); printf("%d ",ans);*/ goto LABEL2; continue; }else { goto LABEL1; } } // cout<<opt<<" "<<x<<" "<<y<<endl; } }