求助,洛谷上过了,SPOJ上WA
查看原帖
求助,洛谷上过了,SPOJ上WA
383791
Others楼主2023/1/14 19:54
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005,inf=0x3f3f3f3f3f3f3f3f;
struct edge {
    int to,w;
};vector<edge> G[N];
struct node {
    int l,r,lc,rc,dl,dr,dm;
}tr[N<<2];int tot,rt[N];
multiset<int> st[N];
int dis[N],ord[N],nord,fa[N],son[N],pos[N],c[N],siz[N],dep[N],top[N],n,m,u,v,w,ed[N];
char op[15];
struct Others {
    int Tr[N<<2];
    void pushup(int p) {
        Tr[p]=max(Tr[p<<1],Tr[p<<1|1]);
    }
    void build(int l,int r,int p) {
        if(l==r) {
            if(rt[ord[l]]) Tr[p]=tr[rt[ord[l]]].dm;
            else Tr[p]=-inf;
            return ;
        }
        int mid=l+r>>1;
        build(l,mid,p<<1),build(mid+1,r,p<<1|1);
        pushup(p);
    }
    void update(int x,int l,int r,int p) {
        if(l==r) {
            if(rt[ord[l]]) Tr[p]=tr[rt[ord[l]]].dm;
            else Tr[p]=-inf;
            return ;
        }
        int mid=l+r>>1;
        if(x<=mid) update(x,l,mid,p<<1);
        else update(x,mid+1,r,p<<1|1);
        pushup(p);
    }
}T;
void pushup(int p) {
    int mid=tr[p].l+tr[p].r>>1;
    tr[p].dl=max(tr[tr[p].lc].dl,tr[tr[p].rc].dl+dis[ord[mid+1]]-dis[ord[tr[p].l]]);
    tr[p].dr=max(tr[tr[p].rc].dr,tr[tr[p].lc].dr+dis[ord[tr[p].r]]-dis[ord[mid]]);
    tr[p].dm=max(max(tr[tr[p].lc].dm,tr[tr[p].rc].dm),tr[tr[p].lc].dr+tr[tr[p].rc].dl+dis[ord[mid+1]]-dis[ord[mid]]);
}
void build(int l,int r,int p) {
    tr[p].l=l,tr[p].r=r;
    if(l==r) {
        for(const auto &lxl:G[ord[l]]) 
            if(lxl.to!=fa[ord[l]]&&lxl.to!=son[ord[l]]) {
                st[ord[tr[p].l]].insert(tr[rt[lxl.to]].dl+lxl.w);
			}
        if(st[ord[tr[p].l]].size()) tr[p].dl=tr[p].dr=max(0ll,(*st[ord[tr[p].l]].rbegin()));
        else tr[p].dl=tr[p].dr=0;
        if(st[ord[tr[p].l]].size()) tr[p].dm=max(0ll,(*st[ord[tr[p].l]].rbegin()));
        else tr[p].dm=0;
        if(st[ord[tr[p].l]].size()>1) tr[p].dm=max(0ll,(*st[ord[tr[p].l]].rbegin())+(*(++st[ord[tr[p].l]].rbegin())));
        return ;
    }
    int mid=l+r>>1;
    tr[p].lc=++tot;
    tr[p].rc=++tot;
    build(l,mid,tr[p].lc),build(mid+1,r,tr[p].rc);
    pushup(p);
}
void update(int p,int x) {
    if(tr[p].l==tr[p].r) {
        if(c[ord[tr[p].l]]) {
            if(st[ord[tr[p].l]].size()) tr[p].dl=tr[p].dr=(*st[ord[tr[p].l]].rbegin());
            else tr[p].dl=tr[p].dr=-inf;
            if(st[ord[tr[p].l]].size()>1) tr[p].dm=(*st[ord[tr[p].l]].rbegin())+(*(++st[ord[tr[p].l]].rbegin()));
            else tr[p].dm=-inf;
        }else {
            if(st[ord[tr[p].l]].size()) tr[p].dl=tr[p].dr=max(0ll,(*st[ord[tr[p].l]].rbegin()));
            else tr[p].dl=tr[p].dr=0;
            if(st[ord[tr[p].l]].size()) tr[p].dm=max(0ll,(*st[ord[tr[p].l]].rbegin()));
            else tr[p].dm=0;
            if(st[ord[tr[p].l]].size()>1) tr[p].dm=max(0ll,(*st[ord[tr[p].l]].rbegin())+(*(++st[ord[tr[p].l]].rbegin())));
        }
        return ;
    }
    if(x<=tr[tr[p].lc].r) update(tr[p].lc,x);
    else update(tr[p].rc,x);
    pushup(p);
}
void dfs1(int p) {
    siz[p]=1,dep[p]=dep[fa[p]]+1;
    for(const auto &lxl:G[p]) {
        if(lxl.to!=fa[p]) {
            fa[lxl.to]=p;
            dis[lxl.to]=dis[p]+lxl.w;
            dfs1(lxl.to);
            siz[p]+=siz[lxl.to];
            if(siz[lxl.to]>siz[son[p]]) son[p]=lxl.to;
        }
    }
}
void dfs2(int p,int Top) {
    ord[pos[p]=++nord]=p;
    top[p]=Top;
    if(son[p]) {
        dfs2(son[p],Top);
    }else ed[top[p]]=pos[p];
    for(const auto &lxl:G[p]) 
        if(lxl.to!=son[p]&&lxl.to!=fa[p]) 
            dfs2(lxl.to,lxl.to);
}
void dfs3(int p) {
    for(const auto &lxl:G[p]) {
        if(lxl.to!=fa[p]&&lxl.to!=son[p]) {
            dfs3(lxl.to);
        }
    }
    if(son[p]) dfs3(son[p]);
    if(p!=son[fa[p]]) build(pos[p],ed[p],rt[p]=++tot);
}
void change(int u) {
    c[u]^=1;
    while(top[u]!=1) {
        st[fa[top[u]]].erase(st[fa[top[u]]].find(tr[rt[top[u]]].dl+dis[top[u]]-dis[fa[top[u]]]));
        update(rt[top[u]],pos[u]);
        T.update(pos[top[u]],1,n,1);
        st[fa[top[u]]].insert(tr[rt[top[u]]].dl+dis[top[u]]-dis[fa[top[u]]]);
        u=fa[top[u]];
    }
    update(rt[top[u]],pos[u]);
    T.update(pos[top[u]],1,n,1);
}
signed main() {
    scanf("%d",&n);
    for(int i=1;i<n;i++) {
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back((edge){v,w});
        G[v].push_back((edge){u,w});
    }
    dfs1(1),dfs2(1,1),dfs3(1);
    T.build(1,n,1);
    scanf("%d",&m);
    for(int pp=1;pp<=m;pp++) {
        scanf("%s",op);
        if(op[0]=='A') {
            if(T.Tr[1]<-1000000000ll) printf("They have disappeared.\n");
            else printf("%d\n",T.Tr[1]);
        }else {
            scanf("%d",&u);
            change(u);
        }
    }
    return 0;
}
2023/1/14 19:54
加载中...