题解洛谷 P4695 【[PA2017]Banany】

考虑用动态点分治来解决像本题这样带修的树上路径问题。

首先对原树进行点分治，建出点分树，在点分树每个节点上用动态开点线段树来维护以该节点为起点，到其点分树子树中每个节点的利润。

查询时只需在点分树上当前所在节点往上跳父亲，在其到点分树根节点的链上的每个节点的线段树上查询。跳到一个节点时，在线段树上查询除了当前节点的利润最大值，同时加上其到当前节点的花费。

修改点权只需在点分树上往上跳父亲，在线段树上单点修改即可。

考虑边权的修改影响的是当前根所对应的一个子树，对于边权的修改，从其两个端点在点分树上深度更大，即点分治递归层数更深的点开始往上跳父亲，每次修改在原树上以当前节点为根，深度更浅的那个端点。

点分树上每个节点的线段树在维护时以节点的 \(dfs\) 序为下标，修改子树信息只需在线段树上区间修改即可。

\(code:\)

#include<bits/stdc++.h>

#define maxn 100010

#define maxm 200010

#define maxt 3500010

#define inf 1000000000000000

#define mid ((l+r)>>1)

#define mk make_pair

using namespace std;

typedef long long ll;

template<typename T> inline void read(T &x)

{

    x=0;char c=getchar();bool flag=false;

    while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

    if(flag)x=-x;

}

int n,q,tree_cnt,dfn_cnt,tot,root,pos=1;

int fa[maxn],ma[maxn],siz[maxn],num[maxn],d[maxn];

int rt[maxn],ls[maxt],rs[maxt],in[20][maxn],out[20][maxn];

ll v[maxn],tag[maxt];

bool vis[maxn];

map<pair<int,int>,ll> w;

struct edge

{

    int to,nxt;

    ll v;

}e[maxm];

int head[maxn],edge_cnt;

void add(int from,int to,ll val)

{

    e[++edge_cnt]=(edge){to,head[from],val};

    head[from]=edge_cnt;

}

struct node

{

    ll val;

    int id;

}t[maxt];

bool operator <(const node &a,const node &b)

{

    if(a.val==b.val) return a.id>b.id;

    return a.val<b.val;

}

void pushtag(int cur,ll v)

{

    t[cur].val+=v,tag[cur]=v;

}

void pushdown(int cur)

{

    if(!tag[cur]) return;

    pushtag(ls[cur],tag[cur]),pushtag(rs[cur],tag[cur]),tag[cur]=0;

}

void insert(int l,int r,int pos,ll v,int id,int &cur)

{

    if(!cur) cur=++tree_cnt;

    if(l==r)

    {

        t[cur]=(node){v,id};

        return;

    }

    if(pos<=mid) insert(l,mid,pos,v,id,ls[cur]);

    else insert(mid+1,r,pos,v,id,rs[cur]);

    t[cur]=max(t[ls[cur]],t[rs[cur]]);

}

void modify(int L,int R,int l,int r,ll v,int &cur)

{

    if(!cur) cur=++tree_cnt;

    if(L<=l&&R>=r)

    {

        pushtag(cur,v);

        return;

    }

    pushdown(cur);

    if(L<=mid) modify(L,R,l,mid,v,ls[cur]);

    if(R>mid) modify(L,R,mid+1,r,v,rs[cur]);

    t[cur]=max(t[ls[cur]],t[rs[cur]]);

}

node query(int L,int R,int l,int r,int cur)

{

    if(L>R||!cur) return (node){-inf,0};

    if(L<=l&&R>=r) return t[cur];

    pushdown(cur);

    if(R<=mid) return query(L,R,l,mid,ls[cur]);

    if(L>mid) return query(L,R,mid+1,r,rs[cur]);

    return max(query(L,R,l,mid,ls[cur]),query(L,R,mid+1,r,rs[cur]));

}

void dfs_root(int x,int fath)

{

    siz[x]=1,ma[x]=0;

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        if(vis[y]||y==fath) continue;

        dfs_root(y,x),siz[x]+=siz[y],ma[x]=max(ma[x],siz[y]);

    }

    ma[x]=max(ma[x],tot-siz[x]);

    if(ma[x]<ma[root]) root=x;

}

void dfs_dis(int x,int fath,ll dis,int id)

{

    in[d[id]][x]=++dfn_cnt,insert(1,num[id],dfn_cnt,v[x]-dis,x,rt[id]);

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        if(vis[y]||y==fath) continue;

        dfs_dis(y,x,dis+e[i].v,id);

    }

    out[d[id]][x]=dfn_cnt;

}

void solve(int x,int depth)

{

    int now=tot;

    d[x]=depth,vis[x]=true,num[x]=now,dfn_cnt=0,dfs_dis(x,0,0,x);

    for(int i=head[x];i;i=e[i].nxt)

    {

        int y=e[i].to;

        if(vis[y]) continue;

        root=0,tot=siz[y];

        if(siz[y]>siz[x]) tot=now-siz[x];

        dfs_root(y,x),fa[root]=x,solve(root,depth+1);

    }

}

int main()

{

    read(n),read(q);

    for(int i=1;i<=n;++i) read(v[i]);

    for(int i=1;i<n;++i)

    {

        int x,y;

        ll v;

        read(x),read(y),read(v);

        add(x,y,v),add(y,x,v);

        if(x>y) swap(x,y);

        w[mk(x,y)]=v;

    }

    tot=ma[0]=n,dfs_root(1,0),solve(root,1);

    while(q--)

    {

        int opt,x,y,p;

        ll val,t;

        node ans=(node){-inf,0};

        read(opt);

        if(opt==1)

        {

            read(x),read(val);

            for(int i=x;i;i=fa[i])

                modify(in[d[i]][x],in[d[i]][x],1,num[i],val-v[x],rt[i]);

            v[x]=val;

        }

        else

        {

            read(x),read(y),read(val);

            if(x>y) swap(x,y);

            t=w[mk(x,y)]-val,w[mk(x,y)]=val;

            if(d[x]<d[y]) p=x;

            else p=y;

            while(p)

            {

                if(in[d[p]][x]>in[d[p]][y]) modify(in[d[p]][x],out[d[p]][x],1,num[p],t,rt[p]);

                else modify(in[d[p]][y],out[d[p]][y],1,num[p],t,rt[p]);

                p=fa[p];

            }

        }

        for(int i=pos;i;i=fa[i])

        {

            node now=max(query(1,in[d[i]][pos]-1,1,num[i],rt[i]),query(in[d[i]][pos]+1,num[i],1,num[i],rt[i]));

            now.val+=query(in[d[i]][pos],in[d[i]][pos],1,num[i],rt[i]).val-v[pos],ans=max(ans,now);

        }

        printf("%d ",pos=ans.id);

    }

    return 0;

}

巴特西

题解洛谷 P4695 【[PA2017]Banany】

最新文章

热门文章

巴特西

题解 洛谷 P4695 【[PA2017]Banany】

最新文章

热门文章

题解洛谷 P4695 【[PA2017]Banany】