蒟蒻刚学OI，求助！

wxwoo @ 2019-04-12 20:33:48

by wxwoo @ 2019-04-12 20:34:46

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
template<typename T> inline void read(T &x)
{
    char ch;
    T f=1;
    x=0;
    do
    {

        if(ch=='-')

            f=-1;

        ch=getchar();

    }while(!('0'<=ch&&ch<='9'));

    do

    {

        x=(x<<3)+(x<<1)+ch-48;

        ch=getchar();

    }while('0'<=ch&&ch<='9');

    x*=f;

}

const int N=100010;

int wt[N],n;

namespace sgttree

{

    #define ls(p) p<<1

    #define rs(p) p<<1|1

    int ans[N<<2];

    inline void pushup(int p)

    {

        ans[p]=max(ans[ls(p)],ans[rs(p)]);

    }

    void build(int p,int l,int r)

    {

        if(l==r)

        {

            ans[p]=wt[l];

            return;

        }

        int mid=l+r>>1;

        build(ls(p),l,mid);

        build(rs(p),mid+1,r);

        pushup(p);

    }

    void update(int x,int l,int r,int p,int k)

    {

        if(l==x&&l==r)

        {

            ans[p]=k;

            return;

        }

        int mid=l+r>>1;

        if(x<=mid)

            update(x,l,mid,ls(p),k);

        if(mid<x)

            update(x,mid+1,r,rs(p),k);

        pushup(p);

    }

    int query(int ql,int qr,int l,int r,int p)

    {

        if(ql<=l&&r<=qr)

        {

            return ans[p];

        }

        int mid=l+r>>1,res=-2147483648;

        if(ql<=mid)

            res=max(res,query(ql,qr,l,mid,ls(p)));

        if(mid<qr)

            res=max(res,query(ql,qr,mid+1,r,rs(p)));

        return res;

    }

}

using namespace sgttree;

namespace treesplit

{

    struct edge

    {

        int nxt,to,w;

        #define nxt(n) ed[n].nxt

        #define to(n) ed[n].to

        #define w(n) ed[n].w

    }ed[N<<1];

    int hed[N],e,we[N];

    int vv[N],uu[N];

    int son[N],fa[N],dep[N],id[N],siz[N],top[N],cnt;

    inline int add(int u,int v,int w)

    {

        to(++e)=v;

        nxt(e)=hed[u];

        w(e)=w;

        hed[u]=e;

    }

    void dfs1(int x,int f,int d)

    {

        son[x]=0;

        dep[x]=d;

        fa[x]=f;

        siz[x]=1;

        int bigson=-1;

        for(int i=hed[x];i;i=nxt(i))

        {

            int y=to(i);

            if(y==f)

                continue;

            we[y]=w(i);

            dfs1(y,x,d+1);

            siz[x]+=siz[y];

            if(bigson<siz[y])

                son[x]=y,bigson=siz[y];

        }

    }

    void dfs2(int x,int t)

    {

        id[x]=++cnt;

        wt[cnt]=we[x];

        top[x]=t;

        if(!son[x])

            return;

        dfs2(son[x],t);

        for(int i=hed[x];i;i=nxt(i))

        {

            int y=to(i);

            if(y==fa[x]||y==son[x])

                continue;

            dfs2(y,y);

        }

    }

    inline void updedge(int x,int k)

    {

        static int u=uu[x],v=vv[x];

        if(fa[v]==u)

            swap(u,v);

        update(id[u],1,n,1,k);

    }

    inline int queryrange(int x,int y)

    {

        int res=-2147483648;

        while(top[x]!=top[y])

        {

            if(dep[top[x]]<dep[top[y]])

                swap(x,y);

            res=max(res,query(id[top[x]],id[x],1,n,1));

            x=fa[top[x]];

        }

        if(dep[x]>dep[y])

            swap(x,y);

        res=max(res,query(id[x]+1,id[y],1,n,1));

        return res;

    }

}

using namespace treesplit;

int main()

{

    read(n);

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

    {

        int u,v,w;

        read(u);

        read(v);

        read(w);

        uu[i]=u;

        vv[i]=v;

        add(u,v,w);

        add(v,u,w);

    }

    char ch[10];

    int a,b;

    dfs1(1,1,1);

    dfs2(1,1);

    build(1,1,n);

    while(1)

    {

        scanf("%s",ch);

        if(ch[0]=='D')

            return 0;

        read(a);

        read(b);

        if(ch[0]=='C')

        {

            updedge(a,b);

        }

        else

        {

            printf("%d\n",queryrange(a,b));

        }

    }

    return 0;

}

by SSerxhs @ 2019-04-12 20:38:47

这什么码风

震惊！行数加倍竟是因为

by NaCly_Fish @ 2019-04-12 20:40:05

这个码风太草了

by wxwoo @ 2019-04-12 20:40:20

我手机敲的......粘过来就这样了

by 雪幽幽 @ 2019-04-12 20:45:54

这不是手机盲敲猪国杀直接提交还对了的wxwoo吗