【NOIP2014】联合权值 树上dp
2024-08-28 05:11:25
题目描述 Description
无向连通图G 有n 个点,n - 1 条边。点从1 到n 依次编号,编号为 i 的点的权值为W i ,每条边的长度均为1 。图上两点( u , v ) 的距离定义为u 点到v 点的最短距离。对于图G 上的点对( u, v) ,若它们的距离为2 ,则它们之间会产生Wu
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?
×Wv 的联合权值。
请问图G 上所有可产生联合权值的有序点对中,联合权值最大的是多少?所有联合权值之和是多少?
输入输出格式 Input/output
输入格式:
输入文件名为link .in。
第一行包含1 个整数n 。
接下来n - 1 行,每行包含 2 个用空格隔开的正整数u 、v ,表示编号为 u 和编号为v 的点之间有边相连。
最后1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。
输出格式:
输出文件名为link .out 。
输出共1 行,包含2 个整数,之间用一个空格隔开,依次为图G 上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007 取余。
输入文件名为link .in。
第一行包含1 个整数n 。
接下来n - 1 行,每行包含 2 个用空格隔开的正整数u 、v ,表示编号为 u 和编号为v 的点之间有边相连。
最后1 行,包含 n 个正整数,每两个正整数之间用一个空格隔开,其中第 i 个整数表示图G 上编号为i 的点的权值为W i 。
输出格式:
输出文件名为link .out 。
输出共1 行,包含2 个整数,之间用一个空格隔开,依次为图G 上联合权值的最大值
和所有联合权值之和。由于所有联合权值之和可能很大,输出它时要对10007 取余。
输入样例:
5
1 2
2 3
3 4
4 5
1 5 2 3 10
1 2
2 3
3 4
4 5
1 5 2 3 10
输出样例:
20 74
思路:
一般的做法,可能采用floyd这种鬼畜的最短路来慢慢搞,当然这样做是会完美T掉的!
所以我们要采取机智的方法,距离为2的话,我们就枚举中间的点,这样,他的任意两个儿子的距离就是2~\(≧▽≦)/~啦啦啦
第一问答案,就是枚举每个点的第一大和第二大的儿子,相乘求最大就好
第二问答案我们得化简一下,比如有a有三个儿子,那么答案就是cb,cd,bd,然后稍微推广一下,就知道答案是 ((∑儿子)^2-∑(儿子)^2)/2,然后利用前缀和思想维护一下,就好啦
~\(≧▽≦)/~啦啦啦
代码:
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
const int inf=0x7fffffff; //无限大
//************************************************************************************** vector<int> point[maxn];
void add_edge(int a,int b)
{
point[a].push_back(b);
point[b].push_back(a);
}
ll h[maxn];
int main()
{
int n,a,b;
scanf("%d",&n);
for(int i=;i<n-;i++)
{
scanf("%d%d",&a,&b);
add_edge(a,b);
}
for(int i=;i<=n;i++)
scanf("%d",&h[i]);
ll ans1=,ans2=;
for(int i=;i<=n;i++)
{
ll max_num=,sum=;
for(int j=;j<point[i].size();j++)
{
int now=point[i][j];
ans1=max(ans1,max_num*h[now]);
ans2=(ans2+sum*h[now]+mod)%mod;
max_num=max(max_num,h[now]);
sum+=h[now];
}
}
cout<<ans1<<" "<<(ans2*+mod)%mod<<endl;
}
最新文章
- Twproject Gantt开源甘特图功能扩展
- web前端面试总结
- 《Entity Framework 6 Recipes》中文翻译系列 (7) -----第二章 实体数据建模基础之拆分实体到多表以及拆分表到多实体
- linux下编译安装vim7.4并安装clang_complete插件
- 使用 CSS3 打造一组质感细腻丝滑的按钮
- pdo封装类
- 一、PHP MongoDB Windows7_64位安装与配置
- discuz 模拟批量上传附件发帖
- JPA中的@MappedSuperclass
- EventLog实现事件日志操作
- 让你的java开发变得如此 Smart
- 服务器响应HTTP请求状态码(转)
- 51单片机GPIO口模拟串口通信
- Python存储系统(Memcached)
- day7-基础函数的学习(二)
- qemu与libvirt编译与安装
- vue实现pc端无限加载功能
- javascript隐式原型
- 怎样制作爽心的 dashboard ?
- IdentityServer4 接口说明