题解 P3647 【[APIO2014]连珠线】

2019-11-12 15:47:09


让我来写一篇全网第一篇link 和 cut的换根DP

复杂度(nlogn)

因为max没有逆运算。。。。。

首先一个坑点是

连边方式只能是son -> x -> f[x]

不然会出问题详细见cmd2001大佬的样例

(因为只能是一个新节点和其他一出现的节点连边)

那么dp方程易得

f[x][0]+=max(f[y][1]+w,f[y][0]);

f[x][1]=max(f[x][1],f[y][0]+w-max(f[y][0],f[y][1]+w));

考虑换根那么cut就是跑去贡献

link就是加上贡献

开一个multiset维护一下最大值就ok了

附代码

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int x=0,f=1;
    char p=getchar();
    while(!isdigit(p)){
        if(p=='-') f=-1;
        p=getchar();
    } 
    while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
    return x*f;
}  

const int maxn=2e5+5;

int n,head[maxn],ver[maxn<<1],nxt[maxn<<1];
int edge[maxn<<1],cnt,f[maxn][2],ans;
multiset<int> s[maxn]; 
multiset<int>  :: iterator it;

inline void add(int x,int y,int z){
    nxt[++cnt]=head[x];
    head[x]=cnt;
    ver[cnt]=y;
    edge[cnt]=z;
}

inline void dfs_pre(int x,int fa){
    f[x][1]=-1e9;f[x][0]=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        dfs_pre(y,x);
        f[x][0]+=max(f[y][1]+edge[i],f[y][0]);
        s[x].insert(f[y][0]+edge[i]-max(f[y][0],f[y][1]+edge[i]));
        f[x][1]=max(f[x][1],f[y][0]+edge[i]-max(f[y][0],f[y][1]+edge[i]));
    }
    f[x][1]+=f[x][0];
}

inline void cut(int x,int y,int w){
    f[x][1]=-1e9;
    f[x][0]-=max(f[y][1]+w,f[y][0]);
    s[x].erase(s[x].find(f[y][0]+w-max(f[y][0],f[y][1]+w)));
    if(s[x].size()){
        it=s[x].end();
        it--;
        f[x][1]=*it;
    }
    f[x][1]+=f[x][0];
}

inline void link(int x,int y,int w){
    f[x][1]-=f[x][0];
    f[x][0]+=max(f[y][1]+w,f[y][0]);
    f[x][1]=max(f[x][1],f[y][0]+w-max(f[y][0],f[y][1]+w));
    s[x].insert(f[y][0]+w-max(f[y][0],f[y][1]+w));
    f[x][1]+=f[x][0]; 
}

inline void change_root(int root1,int root2,int w){
    cut(root1,root2,w);
    link(root2,root1,w);
}

inline void dfs(int x,int fa){
    ans=max(ans,f[x][0]);
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        change_root(x,y,edge[i]);
        dfs(y,x);
        change_root(y,x,edge[i]);
    }
}

int main(){
    n=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);add(y,x,z);
    }
    dfs_pre(1,0); 
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}