Venus 的博客

Venus 的博客

题解 P4315 【月下“毛景树”】

posted on 2019-01-07 10:58:59 | under 题解 |

树链剖分。俗话说得好,$\text{OI}$ 毒瘤千千万,树剖 $\text{DP}$ 各一半。(纯属瞎扯,很多数据结构也很毒瘤),这道题很明显的是一道树链剖分的题,但因为操作的对象是边权,而树链剖分针对的应该是点权,所以我们要将边权转为点权来做。

此时很明显,我们会想到将一条边的边权转移到它深度更深的端点上,然后进行处理,但此时会有一个问题,也就是在查询路径 $u-v$ 时,$u$ 和 $v$ 的 $lca$ 的权值是它上一条边的权值,并不属于 $u-v$ 这条路径,所以我们在退出 $top[u]\not= top[v]$ 这层循环,进行最后一次操作时应将 $u$ 的 $\text{DFS}$ 序加上 $1$ ,这样就可以忽略 $lca$ 这个点了。

具体原因表述可能不太清楚:在退出循环之后,两个点的位置在同一条重链上,显然,这条重链的 $top$ 就是它们原来的 $lca$,而要忽略 $lca$ ,就是要到达比它深度 $+1$ 的点,这个点的 $\text{DFS}$ 序也显然是比 $lca$ 的 $\text{DFS}$ 序多 $1$。

最后讲一下线段树的注意事项,这题有一个比较少见的操作:区间覆盖,我们多设置一个 $\text{lazytag}$,命名为 $cov$,记录区间覆盖情况,然后在 $\text{pushdown}$ 时先处理这个 $cov$,处理完后不能重新赋值为 $0$ ,而是要赋值为 $-1$,为什么呢?因为区间覆盖的值可能为 $0$,但不可能为负数(毕竟不可能有 $-1$ 个毛毛果),初值也要赋成 $-1$。

#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int cnt,fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],w[MAXN<<1],fr[MAXN<<1];
int n,a[MAXN],t[MAXN<<2],tag[MAXN<<2],cov[MAXN<<2];
int siz[MAXN],son[MAXN],dfn[MAXN],Index,top[MAXN],rk[MAXN],dep[MAXN],faz[MAXN];
string s;
void AddEdge(int u,int v,int c)
{
    to[++cnt]=v;
    nxt[cnt]=fst[u];
    fst[u]=cnt;
    w[cnt]=c;
    fr[cnt]=u;
}
void Dfs1(int u)
{
    siz[u]=1;
    son[u]=0;
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==faz[u]) continue;
        faz[v]=u;
        dep[v]=dep[u]+1;
        rk[v]=w[i];
        Dfs1(v);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v;
    }
}
void Dfs2(int u,int rt)
{
    dfn[u]=++Index;
    top[u]=rt;
    a[Index]=rk[u];
    if(son[u]) Dfs2(son[u],rt);
    for(int i=fst[u];i;i=nxt[i])
    {
        int v=to[i];
        if(v==faz[u] || v==son[u]) continue;
        Dfs2(v,v);
    }
}
void PushUp(int rt)
{
    t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
void PushDown(int rt)
{
    if(~cov[rt])
    {
        cov[rt<<1]=cov[rt<<1|1]=cov[rt];
        t[rt<<1]=t[rt<<1|1]=cov[rt];
        tag[rt<<1]=tag[rt<<1|1]=0;
        cov[rt]=-1;
    }
    tag[rt<<1]+=tag[rt];
    tag[rt<<1|1]+=tag[rt];
    t[rt<<1]+=tag[rt];
    t[rt<<1|1]+=tag[rt];
    tag[rt]=0;
}
void BuildSegmentTree(int rt,int l,int r)
{
    cov[rt]=-1;
    if(l==r)
    {
        t[rt]=a[l];
        return;
    }
    int mid=l+r>>1;
    BuildSegmentTree(rt<<1,l,mid);
    BuildSegmentTree(rt<<1|1,mid+1,r);
    PushUp(rt);
}
void ModifyCover(int rt,int l,int r,int tl,int tr,int val)
{
    if(tl<=l && r<=tr)
    {
        t[rt]=cov[rt]=val;
        tag[rt]=0;
        return;
    }
    PushDown(rt);
    int mid=l+r>>1;
    if(tl<=mid) ModifyCover(rt<<1,l,mid,tl,tr,val);
    if(tr>mid) ModifyCover(rt<<1|1,mid+1,r,tl,tr,val);
    PushUp(rt);
}
void ModifyAdd(int rt,int l,int r,int tl,int tr,int val)
{
    if(tl<=l && r<=tr)
    {
        t[rt]+=val;
        tag[rt]+=val;
        return;
    }
    PushDown(rt);
    int mid=l+r>>1;
    if(tl<=mid) ModifyAdd(rt<<1,l,mid,tl,tr,val);
    if(tr>mid) ModifyAdd(rt<<1|1,mid+1,r,tl,tr,val);
    PushUp(rt);
}
int Query(int rt,int l,int r,int tl,int tr)
{
    if(tl<=l && r<=tr) return t[rt];
    PushDown(rt);
    int mid=l+r>>1,res=0;
    if(tl<=mid) res=max(res,Query(rt<<1,l,mid,tl,tr));
    if(tr>mid) res=max(res,Query(rt<<1|1,mid+1,r,tl,tr));
    return res;
}
void ModifyCoverOnTree(int u,int v,int val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ModifyCover(1,1,n,dfn[top[u]],dfn[u],val);
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ModifyCover(1,1,n,dfn[u]+1,dfn[v],val);
}
void ModifyAddOnTree(int u,int v,int val)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        ModifyAdd(1,1,n,dfn[top[u]],dfn[u],val);
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    ModifyAdd(1,1,n,dfn[u]+1,dfn[v],val);
}
int QueryMaxnOnTree(int u,int v)
{
    int res=0;
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res=max(res,Query(1,1,n,dfn[top[u]],dfn[u]));
        u=faz[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    res=max(res,Query(1,1,n,dfn[u]+1,dfn[v]));
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        AddEdge(x,y,z);
        AddEdge(y,x,z);
    }
    Dfs1(1);
    Dfs2(1,1);
    BuildSegmentTree(1,1,n);
    while(1)
    {
        int x,y,z;
        cin>>s;
        if(s=="Stop") break;
        else
        {
            scanf("%d %d",&x,&y);
            if(s=="Change")
            {
                x<<=1;
                int u=fr[x],v=to[x];
                if(dep[u]>dep[v]) swap(u,v);
                ModifyCoverOnTree(u,v,y);
            }
            else if(s=="Cover")
            {
                scanf("%d",&z);
                ModifyCoverOnTree(x,y,z);
            }
            else if(s=="Add")
            {
                scanf("%d",&z);
                ModifyAddOnTree(x,y,z);
            }
            else if(s=="Max") printf("%d\n",QueryMaxnOnTree(x,y));
        }
    }
    return 0;
}