[WC2018]通道

雨点打透心脏的1/2处 2023-10-11 11:16 48阅读 0赞

[题目][Link 1]

三棵树真的能让人自闭

第一棵树常规做法，直接边分治，处理出每个点到分治边的距离\\(dis\_i\\)，同时黑白染色

第二棵树还是常规做法，直接建虚树，处理出每个点到根的路径和\\(pre\_i\\)

要是两个树我们现在树形\\(dp\\)直接就做了，但是还有第三棵树，我们规定第三棵树上点的点权\\(val\_i=dis\_i+pre\_i\\)，现在的问题转化为对于虚树上的每个节点，从其子树里找两个颜色不同的点，使得这两个点在第三棵树上距离(边权+端点点权)最大

看起来比较令人自闭，但是我们注意到一个重要的条件，边权都为正，也就是说对于**树上每一个点，距离其最远的点一定是树直径的端点**

于是利用这个性质，我们只需要维护同色点形成的直径就好了，异色点取最大值我们直接两条直径四个端点取一下就好了；同色直径直接合并就好了，新的直径的端点只可能是原来的四个端点中的两个，共\\(C\_4^2=6\\)种，大力讨论就好了

使用分裂排序和\\(O(1)LCA\\)可以使得复杂度变为\\(O(nlogn)\\)

代码，生涯无展开最长代码226行

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    inline LL read() {
        char c=getchar();LL x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3ll)+(x<<1ll)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    const int M=maxn*4;
    std::vector<int> son[M];
    std::vector<LL> v[M];
    struct E{int v,nxt;LL w;}e[M<<1];
    int head[M],vis[M],sum[M],Mnow,dfn[maxn];
    int c[2][maxn],tp[2],col[maxn],b[maxn];
    LL val[maxn],ans;
    struct Route{int x,y;LL v;}dp[maxn][2];
    int u[maxn][2],rl[maxn];
    int n,rn,rt,num,S;
    inline void add(int x,int y,LL w) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;
    }
    void dfs1(int x,int fa) {
        for(re int i=head[x];i;i=e[i].nxt) {
            if(e[i].v==fa) continue;
            son[x].push_back(e[i].v),v[x].push_back(e[i].w);
            dfs1(e[i].v,x);
        }
    }
    inline int cmp(int A,int B) {return dfn[A]<dfn[B];}
    struct Tree_3 {
        struct E{int v,nxt;LL w;}e[maxn<<1]; 
        int head[maxn],lg[maxn<<1],f[18][maxn<<1],pos[maxn];
        LL pre[maxn];int deep[maxn];
        int num,tot;
        inline int LCA(int x,int y) {
            x=pos[x],y=pos[y];
            if(x>y) std::swap(x,y);
            int k=lg[y-x+1];
            if(deep[f[k][x]]<deep[f[k][y-(1<<k)+1]]) return f[k][x];
            return f[k][y-(1<<k)+1];
        }
        inline void add(int x,int y,LL w) {
            e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;
        }
        void dfs(int x) {
            f[0][++tot]=x;pos[x]=tot;
            for(re int i=head[x];i;i=e[i].nxt) {
                if(deep[e[i].v]) continue;
                deep[e[i].v]=deep[x]+1;pre[e[i].v]=pre[x]+e[i].w;
                dfs(e[i].v);f[0][++tot]=x;
            }
        }
        inline LL dis(int x,int y) {
            if(x==y) return 0;
            return val[x]+val[y]+pre[x]+pre[y]-2ll*pre[LCA(x,y)];
        }
        inline void build() {
            LL w;int x,y;
            for(re int i=1;i<rn;i++) {
                x=read(),y=read(),w=read();
                add(x,y,w),add(y,x,w);
            }
            deep[1]=1,dfs(1);
            for(re int i=2;i<=tot;i++) lg[i]=lg[i>>1]+1;
            for(re int j=1;j<=lg[tot];j++)
                for(re int i=1;i+(1<<(j-1))<=tot;i++)
                    if(deep[f[j-1][i]]<deep[f[j-1][i+(1<<(j-1))]]) f[j][i]=f[j-1][i];
                        else f[j][i]=f[j-1][i+(1<<(j-1))];
        }
    }T3;
    inline LL get(Route A,Route B) {
        LL t1=T3.dis(A.x,B.y),t2=T3.dis(A.y,B.x);
        LL t3=T3.dis(A.x,B.x),t4=T3.dis(A.y,B.y);
        return max(max(t1,t2),max(t3,t4));
    }
    inline Route merge(Route A,Route B) {
        int x,y;LL v,t;
        if(A.v>B.v) x=A.x,y=A.y,v=A.v;
            else x=B.x,y=B.y,v=B.v;
        t=T3.dis(A.x,B.y);
        if(t>v) x=A.x,y=B.y,v=t;
        t=T3.dis(A.x,B.x);
        if(t>v) x=A.x,y=B.x,v=t;
        t=T3.dis(A.y,B.y);
        if(t>v) x=A.y,y=B.y,v=t;
        t=T3.dis(A.y,B.x);
        if(t>v) x=A.y,y=B.x,v=t;
        return (Route){x,y,v};
    }
    struct Virual_Tree {
        struct E{int v,nxt;LL w;}e[maxn<<1]; 
        int head[maxn],lg[maxn<<1],f[18][maxn<<1],pos[maxn];
        LL pre[maxn];int deep[maxn],top,st[maxn];
        int num,tot,cnt;
        inline int LCA(int x,int y) {
            x=pos[x],y=pos[y];
            if(x>y) std::swap(x,y);
            int k=lg[y-x+1];
            if(deep[f[k][x]]<deep[f[k][y-(1<<k)+1]]) return f[k][x];
            return f[k][y-(1<<k)+1];
        }
        inline void add(int x,int y,LL w) {
            e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;
        }
        void dfs(int x) {
            dfn[x]=++cnt;f[0][++tot]=x;pos[x]=tot;
            for(re int i=head[x];i;i=e[i].nxt) {
                if(deep[e[i].v]) continue;
                deep[e[i].v]=deep[x]+1;pre[e[i].v]=pre[x]+e[i].w;
                dfs(e[i].v);f[0][++tot]=x;
            }
        }
        inline void ins(int x) {
            if(top<1) {st[++top]=x;return;}
            int lca=LCA(st[top],x);
            if(lca==st[top]) {st[++top]=x;return;}
            while(top>1&&dfn[st[top-1]]>=dfn[lca])
                add(st[top-1],st[top],0),top--;
            if(lca!=st[top]) add(lca,st[top],0),st[top]=lca;
            st[++top]=x;
        }
        inline void build() {
            LL w;int x,y;
            for(re int i=1;i<rn;i++) {
                x=read(),y=read(),w=read();
                add(x,y,w),add(y,x,w);
            }
            deep[1]=1,dfs(1);memset(head,0,sizeof(head));
            for(re int i=2;i<=tot;i++) lg[i]=lg[i>>1]+1;
            for(re int j=1;j<=lg[tot];j++)
                for(re int i=1;i+(1<<(j-1))<=tot;i++)
                    if(deep[f[j-1][i]]<deep[f[j-1][i+(1<<(j-1))]]) f[j][i]=f[j-1][i];
                        else f[j][i]=f[j-1][i+(1<<(j-1))];
            for(re int i=1;i<=rn;i++) b[i]=i;
            std::sort(b+1,b+rn+1,cmp);
        }
        inline void get_tree(int l,int r) {
            num=0;top=0;
            if(b[l]!=1) ins(1);
            for(re int i=l;i<=r;i++) val[b[i]]+=pre[b[i]],ins(b[i]),rl[b[i]]=1;
            while(top>1) add(st[top-1],st[top],0),top--;
        }
        void tree_dp(int x) {
            if(rl[x]) {
                u[x][col[x]]=1;
                dp[x][col[x]].x=dp[x][col[x]].y=x;
                dp[x][col[x]].v=0;
            }
            for(re int i=head[x];i;i=e[i].nxt) {
                tree_dp(e[i].v);LL t;
                if(u[e[i].v][0]&&u[x][1]) t=get(dp[x][1],dp[e[i].v][0]),ans=max(ans,t-2ll*pre[x]);
                if(u[e[i].v][1]&&u[x][0]) t=get(dp[x][0],dp[e[i].v][1]),ans=max(ans,t-2ll*pre[x]);
                if(u[e[i].v][0]) {
                    if(!u[x][0]) dp[x][0]=dp[e[i].v][0];
                    else dp[x][0]=merge(dp[x][0],dp[e[i].v][0]);
                    u[x][0]=1;
                }
                if(u[e[i].v][1]) {
                    if(!u[x][1]) dp[x][1]=dp[e[i].v][1];
                    else dp[x][1]=merge(dp[x][1],dp[e[i].v][1]);
                    u[x][1]=1;
                }
            }
        }
        void del(int x) {
            for(re int i=head[x];i;i=e[i].nxt) del(e[i].v);
            head[x]=val[x]=0;u[x][0]=u[x][1]=0,rl[x]=0;
        }
    }T2;
    void getrt(int x,int fa) {
        sum[x]=1;
        for(re int i=head[x];i;i=e[i].nxt) {
            if(vis[i>>1]||e[i].v==fa) continue;
            getrt(e[i].v,x);sum[x]+=sum[e[i].v];
            int now=max(sum[e[i].v],S-sum[e[i].v]);
            if(now<Mnow) Mnow=now,rt=i;
        }
    }
    void dfs2(int x,int fa,int o,LL d) {
        if(x<=rn) col[x]=o,val[x]=d;
        for(re int i=head[x];i;i=e[i].nxt) {
            if(vis[i>>1]||e[i].v==fa) continue;
            dfs2(e[i].v,x,o,d+e[i].w);
        }
    }
    void solve(int x,int s,int l,int r) {
        if(l>r) return;
        Mnow=M,S=s,getrt(x,0);
        if(Mnow==M) return;vis[rt>>1]=1;
        dfs2(e[rt].v,0,0,e[rt].w),dfs2(e[rt^1].v,0,1,0);
        T2.get_tree(l,r);
        T2.tree_dp(1);
        tp[0]=tp[1]=0;T2.del(1);
        for(re int i=l;i<=r;i++) c[col[b[i]]][++tp[col[b[i]]]]=b[i];
        for(re int i=l,k=1;k<=tp[0];i++,k++) b[i]=c[0][k];
        for(re int i=l+tp[0],k=1;k<=tp[1];i++,k++) b[i]=c[1][k];
        int now=s-sum[e[rt].v],k=rt,L=l+tp[0]-1,R=r-tp[1]+1;
        solve(e[k].v,sum[e[k].v],l,L);
        solve(e[k^1].v,now,R,r);
    }
    int main() {
        rn=n=read();LL w;int s[2];
        for(re int x,y,i=1;i<n;i++) {
            x=read(),y=read(),w=read();
            add(x,y,w),add(y,x,w);
        }
        dfs1(1,0);num=1;memset(head,0,sizeof(head));
        for(re int i=1;i<=n;i++) {
            int t=son[i].size();
            if(t<=2) {
                for(re int j=0;j<t;j++)
                    add(i,son[i][j],v[i][j]),add(son[i][j],i,v[i][j]);
                continue;
            }
            s[0]=++n,s[1]=++n;
            add(i,s[0],0),add(s[0],i,0),add(i,s[1],0),add(s[1],i,0);
            for(re int j=0;j<t;j++)
                son[s[j&1]].push_back(son[i][j]),v[s[j&1]].push_back(v[i][j]);
        }
        T2.build();T3.build();
        solve(1,n,1,rn);
        std::cout<<ans;
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11348235.html

[Link 1]: https://www.luogu.org/problem/P4220