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

· · 题解

树剖维护边权裸题。

线段树中维护区间覆盖、区间修改以及区间最大值即可。

代码

#include<bits/stdc++.h>
#define N 100005
#define M N*2
using namespace std;
int head[N],to[M],Next[M],len[M],e,n;
void buid(int u,int v,int l)
{
    Next[++e]=head[u];head[u]=e;to[e]=v;len[e]=l;
}
int eid[N],val[N];
int siz[N],dep[N],wson[N],fa[N];
void dfs(int now)
{
    dep[now]=dep[fa[now]]+1;
    siz[now]=1;
    for(int i=head[now];i;i=Next[i])
    {
        int j=to[i];if(j==fa[now]) continue;
        fa[j]=now;eid[(i+1)/2]=j;val[j]=len[i];
        dfs(j);
        siz[now]+=siz[j];
        if(siz[j]>siz[wson[now]]) wson[now]=j;
    }
}
int id[N],who[N],knt,top[N];
void dfs(int now,int fl)
{
    top[now]=fl;
    id[now]=++knt;who[knt]=now;
    if(!wson[now]) return;
    dfs(wson[now],fl);
    for(int i=head[now];i;i=Next[i])
    {
        int j=to[i];if(j==fa[now]||j==wson[now]) continue;
        dfs(j,j);
    }
}
struct node
{
    int big;
    int co,la;
    void clear()
    {
        co=-1;la=0;
    }
}tre[N*4];
void push(int x,int y)
{
    if(tre[x].co!=-1) tre[y].la=0,tre[y].co=tre[y].big=tre[x].co;
    if(tre[x].la) tre[y].la+=tre[x].la,tre[y].big+=tre[x].la;
}
void down(int now,int lson,int rson)
{
    push(now,lson);
    push(now,rson);tre[now].clear();
}
void update(int now,int lson,int rson)
{
    tre[now].big=max(tre[lson].big,tre[rson].big);
}
void change(int u,int v,int l,int r,int now)
{
    if(u>v) return;
    if(u<=l&&v>=r) return push(0,now);
    int mid=(l+r)>>1,lson=now<<1,rson=lson|1;
    down(now,lson,rson);
    if(v<=mid) change(u,v,l,mid,lson);
    else if(u>mid) change(u,v,mid+1,r,rson);
    else change(u,mid,l,mid,lson),change(mid+1,v,mid+1,r,rson);
    update(now,lson,rson);
}
int ask(int u,int v,int l,int r,int now)
{
    if(u>v) return -(1<<30);
    if(u<=l&&v>=r)  return tre[now].big;
    int mid=(l+r)>>1,lson=now<<1,rson=lson|1;
    down(now,lson,rson);
    if(v<=mid) return ask(u,v,l,mid,lson);
    else if(u>mid) return ask(u,v,mid+1,r,rson);
    else return max(ask(u,mid,l,mid,lson),ask(mid+1,v,mid+1,r,rson));
}
void buid_t(int l,int r,int now)
{
    if(l==r)
    {
        tre[now].big=val[who[l]];tre[now].clear();
        return;
    }
    int mid=(l+r)>>1,lson=now<<1,rson=lson|1;
    buid_t(l,mid,lson);mid++;buid_t(mid,r,rson);
    update(now,lson,rson);tre[now].clear();
}
void Add()
{
    int u,v,w;scanf("%d%d%d",&u,&v,&w);
    tre[0].clear();tre[0].la=w;
    int tu=top[u],tv=top[v];
    while(tu!=tv)
    {
        if(dep[tu]<dep[tv]) swap(tu,tv),swap(u,v);
        change(id[tu],id[u],1,n,1);
        u=fa[tu],tu=top[u];
    }
    if(dep[u]<dep[v]) swap(u,v);
    change(id[v]+1,id[u],1,n,1);
}
void Max()
{
    int u,v;scanf("%d%d",&u,&v);
    int ans=-(1<<30),tu=top[u],tv=top[v];
    while(tu!=tv)
    {
        if(dep[tu]<dep[tv]) swap(tu,tv),swap(u,v);
        ans=max(ans,ask(id[tu],id[u],1,n,1));
        u=fa[tu],tu=top[u];
    }
    if(dep[u]<dep[v]) swap(u,v);
    ans=max(ans,ask(id[v]+1,id[u],1,n,1));
    printf("%d\n",ans);
}
void Change()
{
    int k,w;scanf("%d%d",&k,&w);
    tre[0].clear();tre[0].co=w;
    change(id[eid[k]],id[eid[k]],1,n,1);
}
void Cover()
{
    int u,v,w;scanf("%d%d%d",&u,&v,&w);
    tre[0].clear();tre[0].co=w;
    int tu=top[u],tv=top[v];
    while(tu!=tv)
    {
        if(dep[tu]<dep[tv]) swap(tu,tv),swap(u,v);
        change(id[tu],id[u],1,n,1);
        u=fa[tu],tu=top[u];
    }
    if(dep[u]<dep[v]) swap(u,v);
    change(id[v]+1,id[u],1,n,1);
}
char fl[10];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        int u,v,l;scanf("%d%d%d",&u,&v,&l);
        buid(u,v,l);buid(v,u,l);
    }
    dfs(1);dfs(1,1);
    buid_t(1,n,1);  
    while("MloVtry is Handsome!")
    {
        scanf("%s",fl);
        if(fl[0]=='S') return 0;
        if(fl[0]=='A') Add();
        else if(fl[0]=='M') Max();
        else if(fl[1]=='h') Change();
        else Cover();
    }
}