mag
描述
您将获得一棵由无向边连接的树，树上每个节点都分配了一个魔力值 X X i i 。
路径的魔力值被定义为该路径上节点的魔力值的乘积除以该路径上节点的
数量 。 例如 ， 路径上有两个点 ， 魔力值分别为 3 3 和 和 5 5 ， 那么这条路径的魔力值就
为 为 7.5 （ 3*5/2 ）。
在给定的树中，找到具有最小魔力值的路径并输出该路径的魔力值。
输入
第一行输入包含整数 N N （1 1 ≤N N ≤ 10
6 6 ）。表示树中的节点数。
接下来 1 N-1 行中的每一行包含两个整数，A A i i 和 和 B B i i （1 1 ≤A A i i ，B B i i ≤N N ）。表示每
条边连接的两个节点的编号。
接下来 N N 行中的每一行包含一个整数 X X i i （1 1 ≤X X i i ≤ 10
9 9 ）。表示第 i i 个节点的
魔力值。
输出
以分数 Q P/Q 的形式输出具有最小魔力值的路径的魔力值 （P P 和 和 Q Q 是互质的整
数）。
保证 P P 和 和 Q Q 小于 10
18 。
分数分布
对于 20% 的数据，N N ≤ 1000 。
对于另外 30% 的数据，不会有节点和超过 2 2 个其他节点直接相连。
样例输入 1
2
1 2
3
4
样例输出 1
3/1
样例输入 2
5
1 2
2 4
1 3
5 2
2
1
1
1
3
样例输出 2
1/2
思路
假设4的权值为2 其余全为1
则有 魔力值（1,6） = ２／（ｘ＋ｙ＋１）［ｘ为５到６长度，ｙ为１到３长度］
(5,6)＝1/x (1,3) = 1/y
易证 答案定为一条只含一或中间有一个二的链或一个单点
代码
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long lol;
const int MAXN = 1000001;
vector<int> Edge[MAXN];
int dp[MAXN][3],Magic[MAXN],minl = 1e9 + 1;
//dp是树形dp
bool vis[MAXN];
lol ans1,ans2;
inline void prepare(int x)
{
int i,q1,q2;
q1 = q2 = 0;
if(Magic[x] == 1) dp[x][0] = 1;
//dp[][0]记录到此点为止最长的只含一的单链
for(i = 0;i < Edge[x].size();i++)
{
if(vis[Edge[x][i]]) continue;
vis[Edge[x][i]] = 1;
//先搜再算 防止值错
prepare(Edge[x][i]);
if(dp[Edge[x][i]][0] > q1) q2 = q1,q1 = dp[Edge[x][i]][0];
//记以该点为根的最大只含一的单链长度
else if(dp[Edge[x][i]][0] > q2) q2 = dp[Edge[x][i]][0];
//同上记次孝小
if(Magic[x] == 1) dp[x][0] = max(dp[x][0],1 + dp[Edge[x][i]][0]);//更新
dp[x][1] = max(dp[x][0],max(dp[x][1],dp[Edge[x][i]][1]));
//记以该点为根的树上最长只含一单链
}
if(Magic[x] == 1) dp[x][1] = max(dp[x][1],q1 + q2 + 1);
//可能链中途过该点，两端在该点下
}
inline void prepare2(int x)
{
int i;
int q1,q2,q3,q4,it[5] = {};
q1 = q2 = q3 = q4 = 0;
for(i = 0;i < Edge[x].size();i++)
{
if(vis[Edge[x][i]]) continue;
vis[Edge[x][i]] = 1;
prepare2(Edge[x][i]);
if(dp[Edge[x][i]][1] > q1) it[2] = it[1],q2 = q1,q1 = dp[Edge[x][i]][1],it[1] = i;
//记最大和次大
else
if(dp[Edge[x][i]][1] > q2) q2 = dp[Edge[x][i]][1],it[2] = i;
if(dp[Edge[x][i]][2] > q3) it[4] = it[3],q4 = q3,q3 = dp[Edge[x][i]][2],it[3] = i;
else if(dp[Edge[x][i]][2] > q4) q4 = dp[Edge[x][i]][2],it[4] = i;
if(Magic[x] == 1) {dp[x][2] = max(dp[x][2],(dp[Edge[x][i]][2]? dp[Edge[x][i]][2]:-1) + 1);dp[x][1] = max(dp[x][1],1 + dp[Edge[x][i]][1]);}
// 更新
if(Magic[x] == 2) dp[x][2] = max(dp[x][2],1 + dp[Edge[x][i]][1]);
dp[x][0] = max(dp[x][0],dp[Edge[x][i]][0]);
}
if(Magic[x] == 2)dp[x][2] = max(dp[x][2],1),dp[x][0] = max(dp[x][0],1 + q1 + q2);
if(Magic[x] == 1)
{
dp[x][1] = max(dp[x][1],1);
if(it[3] != it[1])
dp[x][0] = max(dp[x][0],q3 + q1 + 1);
else dp[x][0] = max(dp[x][0],max(q4 + q1 + 1,q3 + q2 + 1));
}
dp[x][0] = max(dp[x][0],dp[x][2]);
//dp[][2]记到该点为止最长只含一个二的单链
//dp[][1]记到该点为止最长只含一单链
//dp[][0]记以该点为根的树上最长最长只含一个二的单链
}
int main()
{
freopen("mag.in","r",stdin);
freopen("mag.out","w",stdout);
int i,n,u,v;
scanf("%d",&n);
for(i = 1;i < n;i++)
{
scanf("%d%d",&u,&v);
Edge[u].push_back(v);
Edge[v].push_back(u);
}
//建树
for(i = 1;i <= n;i++)
{
scanf("%d",&Magic[i]);
if(Magic[i] < minl) minl = Magic[i];
}
//找最小单点
ans1 = minl,ans2 = 1;
vis[1] = 1;
prepare(1);
//找只含一的单链
if(dp[1][1] > 0)
if(1.0 / dp[1][1] < ans1 * 1.0 / ans2)
ans1 = 1,ans2 = dp[1][1];
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
vis[1] = 1;
prepare2(1);
//找只含一个二和若干个一的单链
if(dp[1][0] > 0)
if(2.0 / dp[1][0] < ans1 * 1.0 / ans2)
ans1 = 2,ans2 = dp[1][0];
printf("%lld/%lld",ans1,ans2);
return 0;
}
相关阅读
注：本文章转载自：http://www.33lc.com/article/7364.htmlC#中的List怎么样？List<T>类是ArrayList类的泛型等效类，该类使用大小可按需
相关文献（[url]http://www.ibm.com/developerworks/cn/web/wa-rails1/#N1007C[/url]）许多应用程序似乎都花费很多时间做重复的事情
关于导致java.lang.InstantiationException异常的原因
这个异常多半是由于通过反射在实例化的时候，对应的类里面覆盖了无参构造而导致无法实例化，由于创建类的时候，默认有一个无参构造，前提
aSRVCC = SRVCC during alerting stage bSRVCC = SRVCC before alerting stage eSRVCC = enhanced SRVCC, which is a network
因为国内服务器域名解析的问题， 很多同学找不到VMware软件的下载官网。博主找了很久找到了该网址，可以直接访问官网：https://www.vmw