义乌中学暑假集训 2021.07.15 C

(Updated: )
oi
,

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

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

$n\leq 10^5$。

Sol

换根 DP。

考虑两条路径的形态。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}