义乌中学暑假集训 2021.07.15 C
15 集训 暑假 中学 义乌 2021.07
2023-06-13 09:12:49 时间
义乌中学暑假集训 2021.07.15 C
白云有一颗 n 个节点的树,每个点有一个点权
白兔需要找到两条点不相交的路径,要求最大化这两条路径覆盖点的点权和
n\leq 10^5。
Sol
换根 DP。
考虑两条路径的形态。
- 从两个子树中各抽出一条链。
- 在一棵子树中抽一条经过根的链,再在剩余的儿子的子树中抽一条链。
- 在一棵子树中抽一条子树内的链,再在经过这个子树的父亲抽一条链。
然后维护一下每个点到叶子节点最长链、次长链、子树内最长链、经过子树的父亲最长链即可。
#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;
}
相关文章
- 操作系统内存换出---15
- 大厂-分布式专栏 15 如何解决消息重复,保证消息顺序问题
- 15-基于Nginx构建Tomcat集群
- iOS 15 format新方法
- JDK 15软件下载和安装教程
- 7月VR/AR行业投融资报:全球完成15笔,总金额超6亿元人民币
- 科技巨头开年15天裁员2.5万人!硅谷陷寒冬,每天1600人失业
- AMD猛攻数据中心市场,拿下15年来最高份额,英特尔DCG收入下滑20%
- 【愚公系列】2023年04月 Halcon机器视觉-15种常用缺陷检测实例
- 苹果在iOS 15里添加两步验证器相关功能 支持云同步而且可以自动粘贴验证码
- Fedora 15安装Unetbootin制作USB启动盘
- 15年来首次拥抱AMD!Alienware m15 R5锐龙游戏本图赏
- 都说Djnago框架重,那就让哥用15行代码写个django web程序!
- 为什么 TPU 运算速度比普通的 GPU、CPU 组合快 15-30 倍?
- 苹果发布HomePod 15 beta5加入空间音效和无损播放功能
- javascript身份证号码验证函数(可辨真伪,支持15或18位身份证号)测试误差为0