P4315 【月下“毛景树”】

2018-03-28 21:55:49


一道毒瘤树链剖分

主要思想就是把边权化为点权

与P1505 旅游有些类似

先进行dfs,之后枚举编号为奇数的边

使奇数边的to比from的深度大

然后把边权存为to的点权即可

维护一个区间加法标记和一个区间覆盖标记

接下来就是普通线段树操作了

我才不会说我少打一个pushdown调了两个小时

感谢@da32s1da 大佬的帮助!

丑陋的代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
using namespace std;
const int N=1e5+5;
struct edge
{
    int from,to,nxt,dis;
}edge[N<<1];
int n,num,head[N],fa[N],son[N],tot[N],tag[N<<2];
int cnt,idx[N],top[N],dep[N],w[N],maxn[N<<2],lazy[N<<2];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline void add_edge(int from,int to,int dis)
{
    edge[++num].nxt=head[from];
    edge[num].from=from;
    edge[num].to=to;
    edge[num].dis=dis;
    head[from]=num;
}
void dfs(int k,int father,int deep)
{
    int bigson=0;
    fa[k]=father; dep[k]=deep; tot[k]=1;
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (v==father) continue;
        dfs(v,k,deep+1); tot[k]+=tot[v];
        if (bigson<tot[v])
        {
            bigson=tot[v]; son[k]=v;
        }
    }
}
void dfs(int k,int tp)
{
    idx[k]=++cnt; top[k]=tp;
    if (!son[k]) return; dfs(son[k],tp);
    for (reg int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if (!idx[v]) dfs(v,v);
    }
}
inline void pushup(int now)
{
    maxn[now]=max(maxn[now<<1],maxn[now<<1|1]);
}
inline void pushdown(int now)
{
    if (tag[now]!=-1)
    {
        maxn[now<<1]=maxn[now<<1|1]=tag[now];
        tag[now<<1]=tag[now<<1|1]=tag[now];
        lazy[now<<1]=lazy[now<<1|1]=0;
        tag[now]=-1;
    }
    if (lazy[now])
    {
        lazy[now<<1]+=lazy[now];
        lazy[now<<1|1]+=lazy[now];
        maxn[now<<1]+=lazy[now];
        maxn[now<<1|1]+=lazy[now];
        lazy[now]=0;
    }
}
void build(int l,int r,int now)
{
    lazy[now]=0; tag[now]=-1;
    if (l==r)
    {
        maxn[now]=w[l]; return;
    }
    int mid=(l+r)>>1;
    build(l,mid,now<<1);
    build(mid+1,r,now<<1|1);
    pushup(now);
}
void outchange(int p,int l,int r,int now,int c)
{
    if (l==r)
    {
        maxn[now]=c; return;
    }
    int mid=(l+r)>>1; pushdown(now);
    if (p<=mid) outchange(p,l,mid,now<<1,c);
    else outchange(p,mid+1,r,now<<1|1,c);
    pushup(now);
}
void inchange(int L,int R,int l,int r,int now,int c)//都修改为一个数  
{
    if (l>R||r<L) return;
    if (l>=L&&r<=R)
    {
        maxn[now]=c; tag[now]=c;
        lazy[now]=0; return;
    }
    int mid=(l+r)>>1; pushdown(now);
    if (mid>=R) inchange(L,R,l,mid,now<<1,c);
    else if (mid<L) inchange(L,R,mid+1,r,now<<1|1,c);
    else
    {
        inchange(L,mid,l,mid,now<<1,c);
        inchange(mid+1,R,mid+1,r,now<<1|1,c);
    }
    pushup(now);
} 
void inchanges(int L,int R,int l,int r,int now,int c)//都加上一个数
{
    if (l>R||r<L) return;
    if (l>=L&&r<=R)
    {
        maxn[now]+=c; lazy[now]+=c; return;
    }
    int mid=(l+r)>>1; pushdown(now);
    if (mid>=R) inchanges(L,R,l,mid,now<<1,c);
    else if (mid<L) inchanges(L,R,mid+1,r,now<<1|1,c);
    else
    {
        inchanges(L,mid,l,mid,now<<1,c);
        inchanges(mid+1,R,mid+1,r,now<<1|1,c);
    }
    pushup(now);
} 
int getmax(int L,int R,int l,int r,int now)
{
    if (l>R||r<L) return -1e9;
    if (l>=L&&r<=R) return maxn[now];
    int mid=(l+r)>>1; pushdown(now);
    if (mid>=R) return getmax(L,R,l,mid,now<<1);
    if (mid<L) return getmax(L,R,mid+1,r,now<<1|1);
    return max(getmax(L,mid,l,mid,now<<1),getmax(mid+1,R,mid+1,r,now<<1|1));
}
inline void treechange(int x,int y,int val)//都修改为一个数
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        inchange(idx[top[x]],idx[x],1,n,1,val);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    inchange(idx[x]+1,idx[y],1,n,1,val);
}
inline void treechanges(int x,int y,int val)//都加上一个数 
{
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        inchanges(idx[top[x]],idx[x],1,n,1,val);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    inchanges(idx[x]+1,idx[y],1,n,1,val);
}
inline int treemax(int x,int y)
{
    int ans=-1e9;
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ans=max(ans,getmax(idx[top[x]],idx[x],1,n,1));
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    return max(ans,getmax(idx[x]+1,idx[y],1,n,1));
}
int main()
{
    n=read();
    for (reg int i=1;i<n;i++)
    {
        int x=read(),y=read(),z=read();
        add_edge(x,y,z);
        add_edge(y,x,z);
    }
    dfs(1,0,1); dfs(1,1);
    for (reg int i=1;i<=num;i+=2)
    {
        int &u=edge[i].from,&v=edge[i].to;
        if (dep[u]>dep[v]) swap(u,v);
        w[idx[v]]=edge[i].dis;
    }
    build(1,n,1);
    while (1)
    {
        char opt[10]; scanf("%s",opt);
        if (opt[0]=='S') break;
        int x=read(),y=read();
        if (opt[0]=='C')
          if (opt[1]=='h') outchange(idx[edge[(x<<1)-1].to],1,n,1,y);
          else treechange(x,y,read());
        if (opt[0]=='A') treechanges(x,y,read());
        if (opt[0]=='M') printf("%d\n",treemax(x,y));
    }
    return 0;
}