Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 5551 Solved: 1624
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为根的子树中的最小防御值。
对于每个opt=3的操作，输出一行代表对应子树的最小点权值。
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
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。
/**************************************************************
Problem: 3083
User: ictsing
Language: C++
Result: Accepted
Time:3324 ms
Memory:239704 kb
****************************************************************/
//BZOJ3083 遥远的国度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mt = 2000000+5;
const int inf = (1<<31)-1 ;
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
int n,m;
int ecnt=0;
int top[mt];
int to[mt<<1],nxt[mt<<1],adj[mt];
int minn[mt<<3],chg[mt<<3];
int fa[mt],val[mt],id[mt],last[mt],dep[mt],opt[mt],fp[mt],sz[mt];
int tim=0;
void adde(int u,int v)
{
ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;
}
void dfs1(int u)
{
sz[u]=1,dep[u]=dep[fa[u]]+1;
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(fa[u]==v) continue;
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>sz[opt[u]])
opt[u]=v;
}
}
void dfs2(int u,int chain)
{
top[u]=chain;id[u]=++tim,fp[tim]=u;
if(opt[u]) dfs2(opt[u],chain);
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(v^opt[u]&&v^fa[u])
dfs2(v,v);
}
last[u]=tim;
}
void pushup(int rt)
{
if(rt) minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
}
void pushdown(int rt)
{
if(chg[rt])
{
minn[rt<<1]=minn[rt<<1|1]=chg[rt];
chg[rt<<1]=chg[rt<<1|1]=chg[rt];
chg[rt]=0;
}
}
void build(int rt,int l,int r)
{
if(l==r)
{
minn[rt]=val[fp[l]];
//cout<<l<<" "<<rt<<" "<<val[l]<<" ??? "<<endl;
chg[rt]=0;
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
//cout<<l<<" "<<r<<" "<<rt<<" "<<minn[rt]<<" tut "<<endl;
}
void change(int rt,int l,int r,int lft,int rgt,int c)
{
//cout<<lft<<" fuck "<<rgt<<endl;
//cout<<rt<<endl;
if(lft<=l&&r<=rgt)
{
minn[rt]=c;
chg[rt]=c;
//if(lft==2) cout<<" qaq "<<minn[rt]<<endl;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(lft<=mid) change(rt<<1,l,mid,lft,rgt,c);
if(rgt>mid) change(rt<<1|1,mid+1,r,lft,rgt,c);
pushup(rt);
//cout<<l<<" "<<r<<" "<<rt<<" "<<minn[rt]<<" qwq "<<endl;
}
void lca_chg(int x,int y,int c)
{
//cout<<x<<" "<<y<<" "<<c<<endl;
while(top[x]^top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,1,n,id[top[x]],id[x],c);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
change(1,1,n,id[y],id[x],c);
}
int que(int rt,int l,int r,int lft,int rgt)
{
if(lft>rgt) return inf;
if(lft<=l&&r<=rgt)
{
return minn[rt];
}
pushdown(rt);
int mid=(l+r)>>1;
int res=inf;
if(lft<=mid) res=min(res,que(rt<<1,l,mid,lft,rgt));
if(rgt>mid) res=min(res,que(rt<<1|1,mid+1,r,lft,rgt));
return res;
}
int root=0;
int main()
{
n=read(),m=read();
for(int i=1;i<=n-1;i++)
{
int u=read(),v=read();
adde(u,v),adde(v,u);
}
for(int i=1;i<=n;i++)
val[i]=read();
int xx;scanf("%d",&xx);root=xx;
dfs1(xx);
dfs2(xx,xx);
build(1,1,n);
while(m--)
{
int opt=read();
if(opt==1) scanf("%d",&root);
else if(opt==2)
{
int u=read(),v=read(),x=read();
//cout<<u<<" "<<v<<" "<<x<<" fuck "<<endl;
lca_chg(u,v,x);
}
else
{
int x=read();
if(x==root) printf("%d\n",que(1,1,n,1,n));
else if(fa[root]==x) printf("%d\n",min(que(1,1,n,1,id[root]-1),last[root]==n?inf:que(1,1,n,last[root]+1,n)));
else if(id[root]>=id[x]&&id[root]<=last[x])
{
int y=root;
while(fa[top[y]]!=x&&top[y]^top[x]) y=fa[top[y]];
if(fa[top[y]]==x) y=top[y];
else y=fp[id[x]+1];
printf("%d\n",min(que(1,1,n,1,id[y]-1),last[y]==n?inf:que(1,1,n,last[y]+1,n)));
}
else printf("%d\n",que(1,1,n,id[x],last[x]));
}
}
return 0;
}
评论