联合权值
联合权值
https://ac.nowcoder.com/acm/problem/16495
题意: 给出n个顶点，n-1条边的树，问节点间距离为2的权值乘积和，最大权值乘积是多少？
思路: 遍历每个节点，每个节点的儿子节点的的距离就是2，把儿子节点的权值乘起来就好。
类似于 ab+ac+ad=a(b+c+d) 的思路去写。
代码：
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma G++ optimize(1)
#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <cassert>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define PI 3.14159265358979323846
#define esp 1e-8
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int dir2[8][2]={{-1,-1},{-1,1},{1,-1},{1,1},{0,-1},{-1,0},{0,1},{1,0}};
template <typename _T>
inline void read(_T &f)
{
f = 0; _T fu = 1; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') { fu = -1; } c = getchar(); }
while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
f *= fu;
}
template <typename T>
void print(T x)
{
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x + 48);
else print(x / 10), putchar(x % 10 + 48);
}
template <typename T>
void print(T x, char t)
{
print(x); putchar(t);
}
const int N=200000+100;
const ll MOD=10007;
int n;
int a[N];
int head[N<<1];
int tot;
int x,y;
struct Node
{
int to;
int e;
}edge[N<<1];
void add_edge(int u,int v)
{
++tot;
edge[tot].e=v;
edge[tot].to=head[u];
head[u]=tot;
}
int main()
{
scanf("%d",&n);
memset(head,-1,sizeof(head));
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&x,&y);
add_edge(x,y),add_edge(y,x);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int maxx=0; //最大联合权值
ll sum=0; //记录总和
for(int i=1;i<=n;i++)
{
int maxx2=0; // 对于点i的儿子的最大权值
ll sum2=0; // 对于点i儿子的权值和
for(int j=head[i];j!=-1;j=edge[j].to)
{
int v=edge[j].e; //v是儿子节点
sum+=sum2*a[v]; //计算出当前i这点的权值和
sum2+=a[v]; //更新点i儿子的权值和
maxx=max(maxx,maxx2*a[v]); //更新最大联合权值
maxx2=max(maxx2,a[v]); //更新当前儿子的最大权值
}
}
printf("%d %lld\n",maxx,(sum*2)%MOD);
return 0;
}
