义乌中学暑假集训 2021.07.15 C

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

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

$n\leq 10^5$。

Sol

换根 DP。

考虑两条路径的形态。

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

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

#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%10+'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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇