Bakser's Blog

我是逗比。

bzoj3083 树链剖分+倍增lca+线段树

| Comments

一开始以为是lct,换根和路径修改貌似都可做
子树查询就陷入了崩坏中。。。
后来发现只要链剖然后在dfs序上乱搞就可以了。。。。换根神马的分类讨论一下。。。

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 100010
#define D 20
#define MIN(a,b) (((a)<(b))?(a):(b))
#define INF 0x7f7f7f7f7f7f7f7fLL
typedef long long LL;
struct hh
{
    int v,next;
}edges[N<<2];
struct seg_tree
{
    LL minn,delta;
    seg_tree():minn(0),delta(0){}
}tree[N<<4];
int n,m,point[N],root,fa[N],dep[N],top[N],tot,son[N],size[N],dfn[N],out[N],f[N][D+2];
LL a[N],val[N];
inline void addedge(int u,int v)
{
    static int en(0);
    edges[++en].next=point[u];
    edges[en].v=v;
    point[u]=en;
}
inline void dfs(int u)
{
    son[u]=0;size[u]=1;
    for(int i=point[u];i;i=edges[i].next)
    if(edges[i].v!=fa[u]&&!size[edges[i].v]){
        fa[edges[i].v]=f[edges[i].v][0]=u;
        dep[edges[i].v]=dep[u]+1;
        dfs(edges[i].v);
        if(size[edges[i].v]>size[son[u]])son[u]=edges[i].v;
        size[u]+=size[edges[i].v];
    }
}
inline void make(int u,int anc)
{
    top[u]=anc;a[dfn[u]=++tot]=val[u];
    if(son[u])
    {
        make(son[u],anc);
        for(int i=point[u];i;i=edges[i].next)
            if(edges[i].v!=fa[u]&&edges[i].v!=son[u])
                make(edges[i].v,edges[i].v);
    }
    out[u]=tot;
}
inline void Init_st()
{
    for(int i=1;i<=D;i++)
    for(int j=1;j<=n;j++)
    f[j][i]=f[f[j][i-1]][i-1];
}
inline void push_down(int x,int l,int r)
{
    if(tree[x].delta&&l!=r)
    {
        tree[x<<1].minn=tree[x<<1].delta=tree[x].delta;
        tree[x<<1^1].minn=tree[x<<1^1].delta=tree[x].delta;
        tree[x].delta=0;
    }
}
inline void push_up(int x,int l,int r)
{
    if(l==r)return;
    push_down(x,l,r);
    tree[x].minn=MIN(tree[x<<1].minn,tree[x<<1^1].minn);
}
inline void build_tree(int x,int l,int r)
{
    if(l==r)
    {
        tree[x].minn=a[l];
        return;
    }
    int mid(l+r>>1);
    build_tree(x<<1,l,mid);
    build_tree(x<<1^1,mid+1,r);
    push_up(x,l,r);
}
inline void change(int x,int l,int r,int L,int R,LL delta)
{
    if(l>=L&&r<=R)
    {
        tree[x].minn=tree[x].delta=delta;
        return;   
    }
    int mid(l+r>>1);
    push_down(x,l,r);
    if(L<=mid)change(x<<1,l,mid,L,R,delta);
    if(R>mid)change(x<<1^1,mid+1,r,L,R,delta);
    push_up(x,l,r);
}
inline LL query(int x,int l,int r,int L,int R)
{
    if(l>=L&&r<=R)return tree[x].minn;
    int mid(l+r>>1);
    LL res(INF),tmp;
    push_down(x,l,r);
    if(L<=mid)tmp=query(x<<1,l,mid,L,R),res=MIN(res,tmp);
    if(R>mid)tmp=query(x<<1^1,mid+1,r,L,R),res=MIN(res,tmp);
    push_up(x,l,r);
    return res;
}
inline int lca(int u,int v)
{
    if(dep[u]<dep[v])swap(u,v);
    for(int i=D;i>=0;i--)
    if(dep[f[u][i]]>=dep[v])
        u=f[u][i];
    if(u==v)return u;
    for(int i=D;i>=0;i--)
        if(f[u][i]!=f[v][i])
            u=f[u][i],v=f[v][i];
    return f[v][0];
}
inline void modify(int x,int y,LL delta)
{
    int f1(top[x]),f2(top[y]);
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])swap(f1,f2),swap(x,y);
        change(1,1,n,dfn[f1],dfn[x],delta);
        x=fa[f1];f1=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    change(1,1,n,dfn[x],dfn[y],delta);
}
inline LL find_subtree(int u)
{
    if(u==root)return query(1,1,n,1,n);
    LL res(INF),tmp;
    int fa(lca(u,root)),t(root);
    if(fa==u)
    {
        for(int i=D;i>=0;i--)
            if(dep[f[t][i]]>dep[u])
                t=f[t][i];
        if(dfn[t]-1)tmp=query(1,1,n,1,dfn[t]-1),res=MIN(res,tmp);
        if(out[t]<n)tmp=query(1,1,n,out[t]+1,n),res=MIN(res,tmp);
        return res;
    }
    else return query(1,1,n,dfn[u],out[u]);
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(point,0,sizeof(point));
    for(int i=1,u,v;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    for(int i=1;i<=n;i++)scanf("%lld",val+i);
    scanf("%d",&root);
    dfs(1);
    make(1,1);
    Init_st();
    build_tree(1,1,n);
    int opt,u,v;
    LL w;
    while(m--)
    {
        scanf("%d%d",&opt,&u);
        if(opt==1)root=u;
        else if(opt==2)
        {
            scanf("%d%lld",&v,&w);
            int fa(lca(u,v));
            modify(u,fa,w);
            modify(v,fa,w);
        }
        else printf("%lld\n",find_subtree(u));
    }
    return 0;
}

Comments

comments powered by Disqus