[luoguP1351] 联合权值(Dfs)
2024-09-07 07:41:59
距离为2的点会产生权值,第一问,只需要在dfs的时候把一个点相邻的点都处理出来就行。
具体处理方式看代码,然而这样只处理了一遍,最后在乘2就好了。
第二问只需要处理一个点相邻的点中最大的和次大的就行。
——代码
#include <cstdio>
#include <cstring>
#include <iostream>
#define LL long long const int MAXN = , p = ;
int n, cnt;
int head[MAXN], to[MAXN << ], next[MAXN << ];
LL max, tot, a[MAXN], sum[MAXN], ans[MAXN], max1[MAXN], max2[MAXN];
bool vis[MAXN]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline LL Max(LL x, LL y)
{
return x > y ? x : y;
} inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void dfs(int u)
{
int i, v;
vis[u] = ;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
ans[u] = (ans[u] + sum[u] * a[v]) % p;
sum[u] = (sum[u] + a[v]) % p;
if(a[v] > max1[u]) max2[u] = max1[u], max1[u] = a[v];
else if(a[v] > max2[u]) max2[u] = a[v];
if(!vis[v]) dfs(v);
}
} int main()
{
int i, x, y;
n = read();
memset(head, -, sizeof(head));
for(i = ; i < n; i++)
{
x = read();
y = read();
add(x, y);
add(y, x);
}
for(i = ; i <= n; i++) a[i] = read();
dfs();
for(i = ; i <= n; i++)
{
tot = (tot + ans[i]) % p;
max = Max(max, max1[i] * max2[i]);
}
printf("%lld %lld\n", max, (tot << ) % p);
return ;
}
最新文章
- AssetsManagerEx 组件使用说明
- Visual Studio 2015 新建MVC项目 Package Manager Console不能使用 (HRESULT: 0x80131500)
- js中==, !==, === ,!=的区别
- 关于angularJS与jquery在使用上的一些感悟
- C# 枚举 字符串 转换
- C++常用库函数
- RandomAccessFile类进行文件加密
- java结合testng,利用yaml做数据源的数据驱动实例
- Fluent动网格【6】:部件变形案例
- Nginx是什么,有什么优点?为什么选择Nginx做web服务器软件?(经典经典)
- testng入门教程3用TestNG执行case的顺序
- 转mysql半主从同步
- pygame学习_part1_pygame写程序前的准备工作
- js实现toFixed截取效果
- 【jQuery】deferred对象了解
- document.compatMode介绍
- 如何安装和使用Karma-Jasmine
- ubuntu下中文输入法安装
- ipk CONTROL 目录的作用
- java 多线程系列---JUC原子类(四)之AtomicReference原子类
热门文章
- bzoj 1579: [Usaco2009 Feb]Revamping Trails 道路升级【分层图+spfa】
- bzoj 4297: [PA2015]Rozstaw szyn【瞎搞】
- robotframework - Edit编辑器
- Storm概念学习系列之storm的可靠性
- Java&;Xml教程(八)使用JDOM将Java对象转换为XML
- Python在云端编程之IPython notebook
- vue项目国际化实现 vue-i18n使用详细教程
- input password密码验证跳转页面
- Apache 和 Nginx 下的 URL 重写
- mysql导出数据到excel的两种方式