2015
04-14

JLUCPC

Dr. Skywind and Dr. Walkoncloud are planning to hold the annual JLU Collegiate Programming Contest. The contest was always held in the college of software in the past. However, they changed their minds and decided to find the most convenient location from all colleges this year.
Each college in JLU is located in one of the N (1 <= N <= 100,000) different locations (labeled as 1 to N) connected by N-1 roads. Any two colleges are reachable to each other. The Contest can be held at any one of these N colleges. Moreover, Road i connects college A_i and B_i (1 <= A_i <=N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). College i has T_i (0 <= T_i <= 1,000) teams participating in the contest.
When choosing the college to hold the Contest, Dr. Skywind wishes to minimize the inconvenience of the chosen location. The inconvenience of choosing college P is the sum of the distance that all teams need to reach college P (i.e., if the distance from college i to college P is 20, then the travel distance is T_i*20). Please help Dr. Skywind and Dr. Walkoncloud to choose the most convenient location for the contest.

There are multiple test cases. For each case, the first line contains a single integer N, indicating the number of colleges. The next N lines describes T_1 to T_n. Then, each of the last N-1 lines will contain 3 integers, namely A_i, B_i and L_i.

There are multiple test cases. For each case, the first line contains a single integer N, indicating the number of colleges. The next N lines describes T_1 to T_n. Then, each of the last N-1 lines will contain 3 integers, namely A_i, B_i and L_i.

3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1

4
5

1.求出每个节点作为根，他的下面节点到他的花费，以及数量。

2.求出每个节点的兄弟节点到他的花费以及数量。

3.求出每个节点除了他下面的节点的所有节点到他的花费和数量。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
//内存挂
const int maxn=100002;
int n,m,cnt[maxn],tn[maxn];///每个点的人数
__int64 dis[maxn];///最后要求结果
struct node
{
__int64 dis;
int v;
}tmp;
vector<node>p[maxn<<1];
void dfs(int u,int fa,__int64 len)
{
int i,j,v;
int sum=p[u].size();
dis[1]+=len*cnt[u];
tn[u]=cnt[u];
for(i=0;i<sum;i++)
{
int v=p[u][i].v;
if(v==fa)continue;
dfs(v,u,len+p[u][i].dis);
tn[u]+=tn[v];
}
}
void dfs1(int u,int fa)
{
int size=p[u].size();
for(int i=0;i<size;i++)
{
int v=p[u][i].v;
__int64 w=p[u][i].dis;
if(v==fa) continue;
dis[v]=dis[u]+(tn[1]-2*tn[v])*w;
///对于一条边，求出这条边上面所以边的长度和和下面所有边的长度和，然后就可以进行转移了
dfs1(v,u);
}
}
int main()
{
int u,v,i,j;
__int64 w;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d",&cnt[i]);
dis[i]=0;
p[i].clear();
}
for(i=1;i<n;i++)
{
scanf("%d%d %I64d",&u,&v,&w);
tmp.v=v,tmp.dis=w;
p[u].push_back(tmp);
tmp.v=u,tmp.dis=w;
p[v].push_back(tmp);
}
dfs(1,-1,0);
__int64 ans=dis[1];
dfs1(1,0);
for(i=2;i<=n;i++)
{
if(ans>dis[i]) ans=dis[i];
}
printf("%I64d\n",ans);
}
return 0;
}
/*
3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1
*/


1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！

3. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

4. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience