Accepted/32728 kb/8252 ms

bzoj3083.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=100005;
vector<int>e[maxn];
typedef vector<int>::iterator vi;
//--线段树
long long seg[maxn*4],laz[maxn*4];
int segl[maxn*4],segr[maxn*4];
const int ls(const int &x){return x<<1;}
const int rs(const int &x){return x<<1|1;}
//--
//--树链剖分
long long va[maxn],val[maxn];
int pos[maxn],fa[maxn],tp[maxn],sz[maxn],dp[maxn],hs[maxn];
int qu[maxn],qf,qt,pn;
int beg[maxn],end[maxn];
void dfs1(int u)
{
    sz[u]=1;
    for (vi v=e[u].begin();v!=e[u].end();v++)
    {
        if (!sz[*v])
        {
            fa[*v]=u;dp[*v]=dp[u]+1;
            dfs1(*v);
            sz[u]+=sz[*v];
            if (sz[*v]>sz[hs[u]])
                hs[u]=*v;
        }
    }
}
void dfs2(int u,int tp)
{
    va[beg[u]=pos[u]=++pn]=val[u];
    ::tp[u]=tp;
//  printf("%d->%lld\n",u,va[pn]);
    if (hs[u])
    {
        dfs2(hs[u],tp);
        for (vi v=e[u].begin();v!=e[u].end();v++)
            if (!pos[*v])
                dfs2(*v,*v);
    }
    end[u]=pn;
}
//--end
void pushdown(int x)
{
    if (laz[x])
    {
        seg[x]=laz[x];
        if (segl[x]<segr[x])
            laz[ls(x)]=laz[rs(x)]=laz[x];
        laz[x]=0;
    }
}
void update(int x)
{
    pushdown(x);
    if (segl[x]<segr[x])
    {
        pushdown(ls(x)),pushdown(rs(x));
        seg[x]=min(seg[ls(x)],seg[rs(x)]);
    }
}
int u,v,n,m;
void build(int x,int l,int r)
{
    segl[x]=l;segr[x]=r;
    if (l==r)
    {
        seg[x]=va[l];
        return;
    }
    int mid=(l+r)/2;
    if (l<=mid)
        build(ls(x),l,mid);
    if (r>mid)
        build(rs(x),mid+1,r);
    update(x);
}
long long query(int x,int l,int r,int ql,int qr)
{
    pushdown(x);
    if (ql<=l && r<=qr)
        return seg[x];
    int mid=(l+r)/2;
    long long ret=0x3f3f3f3f3f3f3f3fll;
    if (ql<=mid)
        ret=min(ret,query(ls(x),l,mid,ql,qr));
    if (qr>mid)
        ret=min(ret,query(rs(x),mid+1,r,ql,qr));
    return ret;
}
void edit(int x,int l,int r,int ql,int qr,int c)
{
    pushdown(x);
    if (ql<=l && r<=qr)
    {
        laz[x]=c;
        pushdown(x);
        return;
    }
    int mid=(l+r)/2;
    if (ql<=mid)
        edit(ls(x),l,mid,ql,qr,c);
    if (qr>mid)
        edit(rs(x),mid+1,r,ql,qr,c);
    update(x);
}
void edit(int u,int v,int c)
{
    while (tp[u]!=tp[v])
        if (dp[tp[u]]>dp[tp[v]])
            edit(1,1,n,pos[tp[u]],pos[u],c),u=fa[tp[u]];
        else
            edit(1,1,n,pos[tp[v]],pos[v],c),v=fa[tp[v]];
    if (dp[u]<dp[v])
        edit(1,1,n,pos[u],pos[v],c);
    else
        edit(1,1,n,pos[v],pos[u],c);
}
int anc[maxn][25];
int lca(int u,int v)
{
    if (dp[u]<dp[v])
        swap(u,v);
    for (int i=20;i>=0;i--)
        if (dp[anc[u][i]]>=dp[v])
            u=anc[u][i];
    if (u==v)
        return u;
    for (int i=20;i>=0;i--)
        if (anc[u][i]!=anc[v][i])
            u=anc[u][i],v=anc[v][i];
    return anc[v][0];
}
int root;
long long query(int v)
{
    if (v==root)
        return query(1,1,n,1,n);
    int lca=::lca(v,root);
    if (lca==v)
    {
        long long ret=0x3f3f3f3f3f3f3f3fll;
        int t=root;
        for (int i=20;i>=0;i--)
            if (dp[anc[t][i]]>dp[v])
                t=anc[t][i];
        if (beg[t]>0)
            ret=min(ret,query(1,1,n,1,beg[t]-1));
        if (end[t]<n)
            ret=min(ret,query(1,1,n,end[t],n));
        return ret;
    }else
        return query(1,1,n,beg[v],end[v]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++)
        scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
    for (int i=1;i<=n;i++)
        scanf("%lld",&val[i]);
    scanf("%d",&root);
    dp[1]=1;
    dfs1(1);dfs2(1,1);
    for (int i=1;i<=n;i++)
        anc[i][0]=fa[i];
    for (int i=1;i<=20;i++)
        for (int j=1;j<=n;j++)
            anc[j][i]=anc[anc[j][i-1]][i-1];
    build(1,1,n);
    int x,v,u;
    long long o;
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&x);
        if (x==1)
            scanf("%d",&u),root=u;
        else if (x==2)
            scanf("%d%d%lld",&u,&v,&o),edit(u,v,o);
        else if (x==3)
            scanf("%d",&v),printf("%lld\n",query(v));
    }
    return 0;
}