义乌中学暑假集训 2021.07.15 C

白云有一颗 n 个节点的树，每个点有一个点权

白兔需要找到两条点不相交的路径，要求最大化这两条路径覆盖点的点权和

nleq 10^5。

Sol

换根 DP。

考虑两条路径的形态。

从两个子树中各抽出一条链。
在一棵子树中抽一条经过根的链，再在剩余的儿子的子树中抽一条链。
在一棵子树中抽一条子树内的链，再在经过这个子树的父亲抽一条链。

然后维护一下每个点到叶子节点最长链、次长链、子树内最长链、经过子树的父亲最长链即可。

代码语言：javascript复制

#include<bits/stdc  .h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10 (c-'0'),c=gc();x*=f;}
I void write(LL x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x '0');}
Cn int N=1e5 10;
int n,a[N],fir[N],nxt[N<<1],son[N<<1],tot;
LL Mx,Ans,f[N],g[N],Mx1,Mx2;
I void Add(CI x,CI y){nxt[  tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i]
I void Dfs(CI x,CI fa){
    RI i,sz=0,Mx1=0,Mx2=0,id1=0,id2=0;for(i=fir[x];i;i=nxt[i]) if(to^fa) sz  ,Dfs(to,x),g[x]=max(g[x],g[to]),f[to]>Mx1?(Mx2=Mx1,id2=id1,Mx1=f[to],id1=to):f[to]>Mx2&&(Mx2=f[to],id2=to);
    if(!Mx1&&!Mx2) return Ans=max(Ans,f[x]=g[x]=a[x]),void();
    f[x]=a[x] f[id1],g[x]=max(g[x],f[x]);
    if(!Mx2) return Ans=max(Ans,f[x]),void();
    g[x]=max(g[x],f[x] f[id2]);
    if(sz==2) return Ans=max(Ans,max(f[x] g[id2],g[id1] a[x] f[id2])),void();
    for(i=fir[x];i;i=nxt[i]) to^fa&&to^id1&&to^id2&&(Ans=max(Ans,max(f[x] f[id2] g[to],max(a[x] f[to] f[id2] g[id1],a[x] f[to] f[id1] g[id2]))));
}
I void Dfs2(CI x,CI fa,LL S){
    RI i,Mx1=0,Mx2=0,id1=0,id2=0;for(i=fir[x];i;i=nxt[i]) if(to^fa) f[to]>Mx1?(Mx2=Mx1,id2=id1,Mx1=f[to],id1=to):f[to]>Mx2&&(Mx2=f[to],id2=to);
    for(i=fir[x];i;i=nxt[i]) if(to^fa) to^id1?(Ans=max(Ans,S f[id1] g[to]),Dfs2(to,x,max(S,f[x]) a[to]),0):(Ans=max(Ans,S f[id2] g[to]),Dfs2(to,x,max(S,f[id2] a[x]) a[to]),0); 
}
int main(){
    RI i,j,x,y;for(read(n),i=1;i<=n;i  ) read(a[i]);
    for(i=1;i<n;i  ) read(x),read(y),Add(x,y),Add(y,x);
    return Dfs(1,0),Dfs2(1,0,a[1]),write(Ans),0;
}

0 人点赞