桃夭 @ 2018-11-02 11:49:31

by 桃夭 @ 2018-11-02 11:49:39

include<cstdio>

include<cstdlib>

include<iostream>

include<cstring>

include<cmath>

include<algorithm>

using namespace std; const long long N=100010; struct edge { long long from,to,Next,val; }edge[N2]; long long n,num,cnt; long long head[N],father[N],son[N],tot[N],idx[N],top[N],dep[N],w[N]; long long tag[N4],Max[N4],lazy[N4]; long long read() { char chr; long long f=1; while (((chr=getchar())<'0')||(chr>'9')) { if (chr=='-') { f=-1; } } long long res=chr-'0'; while (((chr=getchar())>='0')&&(chr<='9')) { res=res10+chr-'0'; } return resf; } void add_edge(long long from,long long to,long long val) { edge[++num].Next=head[from]; edge[num].from=from; edge[num].to=to; edge[num].val=val; head[from]=num; } void dfs(long long k,long long f,long long deep) { long long bigson=0; father[k]=f; dep[k]=deep; tot[k]=1; for (long long i=head[k];i;i=edge[i].Next) { long long v=edge[i].to; if (v==f) { continue; }
dfs(v,k,deep+1); tot[k]+=tot[v]; if (bigson<tot[v]) { bigson=tot[v]; son[k]=v; } } } void dfs(long long k,long long tp) { idx[k]=++cnt; top[k]=tp; if (!son[k]) { return; } dfs(son[k],tp); for (long long i=head[k];i;i=edge[i].Next) { long long v=edge[i].to; if (!idx[v]) { dfs(v,v); } } } void pushup(long long now) { Max[now]=max(Max[now2],Max[now2+1]); } inline void pushdown(long long now) { if (tag[now]!=-1) { Max[now2]=Max[now2+1]=tag[now]; tag[now2]=tag[now2+1]=tag[now]; lazy[now2]=lazy[now2+1]=0; tag[now]=-1; } if (lazy[now]) { lazy[now2]+=lazy[now]; lazy[now2+1]+=lazy[now]; Max[now2]+=lazy[now]; Max[now2+1]+=lazy[now]; lazy[now]=0; } } void build(long long l,long long r,long long now) { lazy[now]=0; tag[now]=-1; if (l==r) { Max[now]=w[l]; return; } long long mid=(l+r)/2; build(l,mid,now2); build(mid+1,r,now2+1); pushup(now); } void outchange(long long p,long long l,long long r,long long now,long long c) { if (l==r) { Max[now]=c; return; } long long mid=(l+r)/2; pushdown(now); if (p<=mid) { outchange(p,l,mid,now2,c); } else { outchange(p,mid+1,r,now2+1,c); } pushup(now); } void inchange(long long L,long long R,long long l,long long r,long long now,long long c) { if ((l>R)||(r<L)) { return; } if ((l>=L)&&(r<=R)) { Max[now]=c; tag[now]=c; lazy[now]=0; return; } long long mid=(l+r)/2; pushdown(now); if (mid>=R) { inchange(L,R,l,mid,now2,c); } else { if (mid<L) { inchange(L,R,mid+1,r,now2+1,c); } else { inchange(L,mid,l,mid,now2,c); inchange(mid+1,R,mid+1,r,now2+1,c); } } pushup(now); } void inchanges(long long L,long long R,long long l,long long r,long long now,long long c) { if ((l>R)||(r<L)) { return; } if ((l>=L)&&(r<=R)) { Max[now]+=c; lazy[now]+=c; return; } long long mid=(l+r)/2; pushdown(now); if (mid>=R) { inchanges(L,R,l,mid,now2,c); } else { if (mid<L) { inchanges(L,R,mid+1,r,now2+1,c); } else { inchanges(L,mid,l,mid,now2,c); inchanges(mid+1,R,mid+1,r,now2+1,c); } } pushup(now); } long long getmax(long long L,long long R,long long l,long long r,long long now) { if ((l>R)||(r<L)) { return -1e9; } if ((l>=L)&&(r<=R)) { return Max[now]; } long long mid=(l+r)/2; pushdown(now); if (mid>=R) { return getmax(L,R,l,mid,now2); } if (mid<L) { return getmax(L,R,mid+1,r,now2+1); } return max(getmax(L,mid,l,mid,now2),getmax(mid+1,R,mid+1,r,now2+1)); } void treechange(long long x,long long y,long long 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=father[top[x]]; } if (dep[x]>dep[y]) { swap(x,y); } inchange(idx[x]+1,idx[y],1,n,1,val); } void treechanges(long long x,long long y,long long 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=father[top[x]]; } if (dep[x]>dep[y]) { swap(x,y); } inchanges(idx[x]+1,idx[y],1,n,1,val); } long long treemax(long long x,long long y) { long long 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=father[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 (long long i=1;i<n;i++) { long long x=read(),y=read(),z=read(); add_edge(x,y,z); add_edge(y,x,z); } dfs(1,0,1); dfs(1,1); for (long long i=1;i<=num;i+=2) { long long &u=edge[i].from,&v=edge[i].to; if (dep[u]>dep[v]) { swap(u,v); } w[idx[v]]=edge[i].val; } build(1,n,1); while (1) { char key[10]; scanf("%s",key); if (key[0]=='D') { break; } long long x=read(),y=read(); if (key[0]=='C') { outchange(idx[edge[(x*2)-1].to],1,n,1,y); } if (key[0]=='Q') { if (x==y) { cout<<0<<"\n"; } printf("%d\n",treemax(x,y)); } } return 0; }

by 桃夭 @ 2018-11-02 11:49:53

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const long long N=100010;
struct edge
{
    long long from,to,Next,val;
}edge[N*2];
long long n,num,cnt;
long long  head[N],father[N],son[N],tot[N],idx[N],top[N],dep[N],w[N];
long long tag[N*4],Max[N*4],lazy[N*4];
long long read()
{
    char chr;
    long long f=1;
    while (((chr=getchar())<'0')||(chr>'9'))
    {
        if (chr=='-')
        {
            f=-1;
        }
    }
    long long res=chr-'0';
    while (((chr=getchar())>='0')&&(chr<='9'))
    {
        res=res*10+chr-'0';
    }
    return res*f;
}
void add_edge(long long from,long long to,long long val)
{
    edge[++num].Next=head[from];
    edge[num].from=from;
    edge[num].to=to;
    edge[num].val=val;
    head[from]=num;
}
void dfs(long long k,long long f,long long deep)
{
    long long bigson=0;
    father[k]=f;
    dep[k]=deep;
    tot[k]=1;
    for (long long i=head[k];i;i=edge[i].Next)
    {
        long long v=edge[i].to;
        if (v==f)
        {
            continue;
        }   
        dfs(v,k,deep+1);
        tot[k]+=tot[v];
        if (bigson<tot[v])
        {
            bigson=tot[v];
            son[k]=v;
        }
    }
}
void dfs(long long k,long long tp)
{
    idx[k]=++cnt;
    top[k]=tp;
    if (!son[k])
    {
        return;
    }
    dfs(son[k],tp);
    for (long long i=head[k];i;i=edge[i].Next)
    {
        long long v=edge[i].to;
        if (!idx[v])
        {
            dfs(v,v);
        }
    }
}
void pushup(long long now)
{
    Max[now]=max(Max[now*2],Max[now*2+1]);
}
inline void pushdown(long long now)
{
    if (tag[now]!=-1)
    {
        Max[now*2]=Max[now*2+1]=tag[now];
        tag[now*2]=tag[now*2+1]=tag[now];
        lazy[now*2]=lazy[now*2+1]=0;
        tag[now]=-1;
    }
    if (lazy[now])
    {
        lazy[now*2]+=lazy[now];
        lazy[now*2+1]+=lazy[now];
        Max[now*2]+=lazy[now];
        Max[now*2+1]+=lazy[now];
        lazy[now]=0;
    }
}
void build(long long l,long long r,long long now)
{
    lazy[now]=0;
    tag[now]=-1;
    if (l==r)
    {
        Max[now]=w[l];
        return;
    }
    long long mid=(l+r)/2;
    build(l,mid,now*2);
    build(mid+1,r,now*2+1);
    pushup(now);
}
void outchange(long long p,long long l,long long r,long long now,long long c)
{
    if (l==r)
    {
        Max[now]=c;
        return;
    }
    long long mid=(l+r)/2;
    pushdown(now);
    if (p<=mid)
    {
        outchange(p,l,mid,now*2,c);
    }
    else
    {
        outchange(p,mid+1,r,now*2+1,c);
    }
    pushup(now);
}
void inchange(long long L,long long R,long long l,long long r,long long now,long long c)
{
    if ((l>R)||(r<L))
    {
        return;
    }
    if ((l>=L)&&(r<=R))
    {
        Max[now]=c;
        tag[now]=c;
        lazy[now]=0;
        return;
    }
    long long mid=(l+r)/2;
    pushdown(now);
    if (mid>=R)
    {
        inchange(L,R,l,mid,now*2,c);
    }
    else
    {
        if (mid<L)
        {
            inchange(L,R,mid+1,r,now*2+1,c);
        }
        else
        {
            inchange(L,mid,l,mid,now*2,c);
            inchange(mid+1,R,mid+1,r,now*2+1,c);
        }
    }
    pushup(now);
} 
void inchanges(long long L,long long R,long long l,long long r,long long now,long long c)
{
    if ((l>R)||(r<L))
    {
        return;
    }
    if ((l>=L)&&(r<=R))
    {
        Max[now]+=c;
        lazy[now]+=c;
        return;
    }
    long long mid=(l+r)/2;
    pushdown(now);
    if (mid>=R)
    {
        inchanges(L,R,l,mid,now*2,c);
    }
    else
    {
        if (mid<L)
        {
            inchanges(L,R,mid+1,r,now*2+1,c);
        }
        else
        {
            inchanges(L,mid,l,mid,now*2,c);
            inchanges(mid+1,R,mid+1,r,now*2+1,c);
        }
    }
    pushup(now);
} 
long long getmax(long long L,long long R,long long l,long long r,long long now)
{
    if ((l>R)||(r<L))
    {
        return -1e9;
    }
    if ((l>=L)&&(r<=R))
    {
        return Max[now];
    }
    long long mid=(l+r)/2;
    pushdown(now);
    if (mid>=R)
    {
        return getmax(L,R,l,mid,now*2);
    }
    if (mid<L)
    {
        return getmax(L,R,mid+1,r,now*2+1);
    }
    return max(getmax(L,mid,l,mid,now*2),getmax(mid+1,R,mid+1,r,now*2+1));
}
void treechange(long long x,long long y,long long 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=father[top[x]];
    }
    if (dep[x]>dep[y])
    {
        swap(x,y);
    }
    inchange(idx[x]+1,idx[y],1,n,1,val);
}
void treechanges(long long x,long long y,long long 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=father[top[x]];
    }
    if (dep[x]>dep[y])
    {
        swap(x,y);
    }
    inchanges(idx[x]+1,idx[y],1,n,1,val);
}
long long treemax(long long x,long long y)
{
    long long 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=father[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 (long long i=1;i<n;i++)
    {
        long long x=read(),y=read(),z=read();
        add_edge(x,y,z);
        add_edge(y,x,z);
    }
    dfs(1,0,1);
    dfs(1,1);
    for (long long i=1;i<=num;i+=2)
    {
        long long &u=edge[i].from,&v=edge[i].to;
        if (dep[u]>dep[v])
        {
            swap(u,v);
        }
        w[idx[v]]=edge[i].val;
    }
    build(1,n,1);
    while (1)
    {
        char key[10];
        scanf("%s",key);
        if (key[0]=='D')
        {
            break;
        }
        long long x=read(),y=read();
        if (key[0]=='C')
        {
            outchange(idx[edge[(x*2)-1].to],1,n,1,y);
        }
        if (key[0]=='Q')
        {
            if (x==y)
            {
                cout<<0<<"\n";
            }
            printf("%d\n",treemax(x,y));
        }
    }
    return 0;
}

by RiverFun @ 2018-11-02 11:50:02

希望更丰富的展现？使用Markdown

by 夢·壹生所愛 @ 2018-11-02 11:54:00

不是妹子，不回答qwq

by 桃夭 @ 2018-11-02 11:54:36

啊我知道了漏了个continue

by 桃夭 @ 2018-11-02 11:55:00

@Steve_braveman 谢谢了qwq

by 花里心爱 @ 2018-11-02 12:00:18

蒟蒻表示 当我看到我的代码超过4k的时候 我就知道我要写挂了qwq

by 桃夭 @ 2018-11-02 12:06:16

@Irressey 写还好，查错的时候可能想死qwq

by 曾宇康 @ 2018-11-02 12:07:16

你为什么要强调你不是妹子

by callG @ 2018-11-02 12:09:41

希望更丰富的展现？使用Markdown