洛谷 P1351 联合权值 —— 树形DP
2024-08-31 15:38:58
题目:https://www.luogu.org/problemnew/show/P1351
树形DP,别忘了子树之间的情况(拐一下距离为2)。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const maxn=2e5+,mod=;
int n,hd[maxn],ct,to[maxn<<],nxt[maxn<<];
ll w[maxn],ans,sum,mxx[maxn],s[maxn];
int rd()
{
int ret=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}
while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return ret*f;
}
void add(int x,int y){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct;}
void dfs(int x,int f)
{
ll ns=,nm=;//不是全局变量!
for(int i=hd[x],u;i;i=nxt[i])
{
if((u=to[i])==f)continue;
dfs(u,x); sum=(sum+s[u]*w[x])%mod;
ans=max(ans,mxx[u]*w[x]);
s[x]+=w[u]; mxx[x]=max(mxx[x],w[u]);
sum=(sum+ns*w[u])%mod; ns+=w[u];
ans=max(ans,nm*w[u]); nm=max(nm,w[u]);
}
}
int main()
{
n=rd();
for(int i=,x,y;i<n;i++)
{
x=rd(); y=rd();
add(x,y); add(y,x);
}
for(int i=;i<=n;i++)w[i]=rd();
dfs(,);
printf("%lld %lld\n",ans,(sum*)%mod);
return ;
}
最新文章
- 使用mac终端生成RSA私钥和公钥文件
- Oracle安装注意点与工具使用简说
- 集合的概念 Stack和Queue Dictionary ArrayList和List<;T>;方法及用法
- phpcms标签使用 —— 系统常量
- Android 日常开发总结的技术经验 60 条
- java 21-13 合并
- 欧拉工程第55题:Lychrel numbers
- pdo 连接数据库 报错 could not find driver 解决方法
- Webstorm 配置与使用 Less
- ViewPager的用法
- bootchart--检测linux启动性能的软件
- php 抽象类abstract
- 在后台业务管理系统中使用Autofac实现微信接口的处理
- date命令转换日期命令提示date: illegal time format
- AngularJS 启动执行过程
- 斯巴达克斯诅咒者之战第三季/全集Spartacus迅雷下载
- 九度 1557:和谐答案 (LIS 变形)
- pymssql
- async await promise 执行时序
- Vue组件的定义方式