| 记录编号 |
455890 |
评测结果 |
AAAAAAAAAAAAAAAAAA |
| 题目名称 |
遥远的国度 |
最终得分 |
100 |
| 用户昵称 |
 LadyLex |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
2.026 s |
| 提交时间 |
2017-10-03 13:36:15 |
内存使用 |
5.65 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
using namespace std;
const int N=100010,inf=0x7fffffff;
inline int min(int a,int b){return a<b?a:b;}
int n,e,adj[N];
struct edge{int zhong,next;}s[N<<1];
inline void add(int qi,int zhong)
{s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;}
int a[N],cnt,l[N],r[N],dfn[N],cur_root;
int heavy[N],size[N],top[N],fa[N],deep[N];
inline void dfs1(int rt,int Vater)
{
fa[rt]=Vater,deep[rt]=deep[Vater]+1,size[rt]=1;
for(register int i=adj[rt];i;i=s[i].next)
if(s[i].zhong!=Vater)
{
dfs1(s[i].zhong,rt),size[rt]+=size[s[i].zhong];
if(size[s[i].zhong]>size[heavy[rt]])
heavy[rt]=s[i].zhong;
}
}
inline void dfs2(int rt,int tp)
{
l[rt]=++cnt,dfn[cnt]=rt,top[rt]=tp;
if(heavy[rt])dfs2(heavy[rt],tp);
for(register int i=adj[rt];i;i=s[i].next)
if(s[i].zhong!=fa[rt]&&s[i].zhong!=heavy[rt])
dfs2(s[i].zhong,s[i].zhong);
r[rt]=cnt;
}
inline int Lca(int a,int b)
{
while(top[a]!=top[b])
{
if(deep[top[a]]<deep[top[b]])a^=b,b^=a,a^=b;
a=fa[top[a]];
}
return deep[a]>deep[b]?b:a;
}
struct node
{
node *ch[2];int minn,mark;
node(){minn=inf,mark=-1;}
inline void update()
{minn=min(ch[0]->minn,ch[1]->minn);}
}*null=new node(),*root;
inline void pushdown(node *&o)
{
if(o->mark!=-1)
{
if(o->ch[0]!=null)o->ch[0]->minn=o->ch[0]->mark=o->mark;
if(o->ch[1]!=null)o->ch[1]->minn=o->ch[1]->mark=o->mark;
o->mark=-1;
}
}
inline node* newnode()
{
node *o=new node();
o->ch[0]=o->ch[1]=null;
return o;
}
inline node* build(int l,int r)
{
node *ret=newnode();int mi=l+r>>1;
if(l==r)ret->minn=a[dfn[l]];
else
ret->ch[0]=build(l,mi),
ret->ch[1]=build(mi+1,r),
ret->update();
return ret;
}
inline void set(node *&o,int l,int r,int L,int R,int val)
{
if(L<=l&&r<=R){o->mark=o->minn=val;return;}
int mi=l+r>>1;pushdown(o);
if(L<=mi)set(o->ch[0],l,mi,L,R,val);
if(mi<R)set(o->ch[1],mi+1,r,L,R,val);
o->update();
}
inline void set(int a,int b,int val)
{
while(top[a]!=top[b])
{
if(deep[top[a]]<deep[top[b]])a^=b,b^=a,a^=b;
set(root,1,n,l[top[a]],l[a],val);
a=fa[top[a]];
}
if(deep[a]<deep[b])a^=b,b^=a,a^=b;
set(root,1,n,l[b],l[a],val);
}
inline int query(node *&o,int l,int r,int L,int R)
{
if(l>r)return inf;
if(L<=l&&r<=R)return o->minn;
pushdown(o);
register int ret=inf,mi=l+r>>1;
if(L<=mi)ret=min(ret,query(o->ch[0],l,mi,L,R));
if(mi<R)ret=min(ret,query(o->ch[1],mi+1,r,L,R));
return ret;
}
inline int Vater(int rt,int a)
{
if(top[a]==top[rt])return heavy[rt];
int ans;
while(top[a]!=top[rt])
ans=top[a],a=fa[top[a]];
return (a==rt)?ans:heavy[rt];
}
inline int query(int rt)
{
if(rt==cur_root)return root->minn;
int lca=Lca(rt,cur_root);
if(lca==rt)
{
lca=Vater(rt,cur_root);
return min(query(root,1,n,1,l[lca]-1),
query(root,1,n,r[lca]+1,n));
}
else return query(root,1,n,l[rt],r[rt]);
}
// fc bbbbb9.ans bbbbb.out
int main()
{
freopen("bbbbb.in","r",stdin);
freopen("bbbbb.out","w",stdout);
// freopen("Ark.in","r",stdin);
// freopen("Royal.out","w",stdout);
register int i,j,m,u,v,x,opt;
scanf("%d%d",&n,&m);
for(i=1;i<n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
for(i=1;i<=n;++i)scanf("%d",&a[i]);
scanf("%d",&cur_root);
dfs1(cur_root,0),dfs2(cur_root,cur_root);
null->ch[0]=null->ch[1]=null;
root=build(1,n);
while(m--)
{
scanf("%d",&opt);
switch(opt)
{
case 1:scanf("%d",&cur_root);break;
case 2:scanf("%d%d%d",&u,&v,&x),set(u,v,x);break;
case 3:scanf("%d",&u),printf("%d\n",query(u));break;
}
}
}