2015
09-17

# The Budget of Traveler

There is a country consisting of n cities. A traveler living in the city with number 1 loves travelling very much. He has made
n-1 travel plans, each plan has a unique destination(except city 1). After a travel, he will go back home. On the way back home,
he will buy gifts for all his friends living in the cities(including the starting city and ending city) he will pass. For some
strange reasons, each city sells only one kind gift. Besides, packing the gifts need some extra cost.
Maybe you are still confused of the description, the following is the details
1. Note that the cities form a connected, undirected and a cyclic graph(in another word the cities form a tree).
2. When he goes back home after a travel, he will always choose the shortest route.
3. The n-1 plans are independent, that means, he will always prepare gifts for his friends ont the route no matter whether he has visited them before.
4. The gifts must be packed, and you must pack them in the city where you buy them.
5. The packing cost is no matter with the number of gifts. That is, packing two gifts cost the same money with packing one.

The first line of the input contains an integer T( T<= 10 ), indicating the number of test cases.
For each test case, the first line contains only one integers n, indicating the number of cities.
The next n lines, each line contains three integers fi, pi, ri, where fi is the number of his friend living in city i, pi is the price of each gift in city i, ri is the packing cost in the city i.
The next of n-1 lines, each line contains two integers ui and vi, indicating that the traveler can go to vi from ui or go to ui from vi.
You can assume 1<=n<=4*105, 1<=fi<=104, 1<=pi,ri<=105, 1<=ui,vi<=n

The first line of the input contains an integer T( T<= 10 ), indicating the number of test cases.
For each test case, the first line contains only one integers n, indicating the number of cities.
The next n lines, each line contains three integers fi, pi, ri, where fi is the number of his friend living in city i, pi is the price of each gift in city i, ri is the packing cost in the city i.
The next of n-1 lines, each line contains two integers ui and vi, indicating that the traveler can go to vi from ui or go to ui from vi.
You can assume 1<=n<=4*105, 1<=fi<=104, 1<=pi,ri<=105, 1<=ui,vi<=n

1
3
1 10000 10000
1 1 20
1 100 1
1 2
1 3

Case #1: 223

dp[i] = dp[j] + (sum[i]-sum[j])*p[i] + r[i]; 转移方程，其中j是i的祖先。

#pragma comment(linker, "/STACK:65536000")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#define INC(x,y) {x+=y;if(x>=mod) x-=mod;}
#define Max(x,y) {if(y>x) x=y;}
#define Min(x,y) {if(y<x) x=y;}
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;

const int N = 500000;
const ll inf = 1e18;
int n;
ll f[N],p[N],r[N],sum[N],num[N],dp[N];
int fa[N][20];
vector<int> e[N];

ll f1(int k,int j) {
return dp[j] - dp[k];
}
ll f2(int k,int j) {
return sum[j] - sum[k];
}
ll g(int i,int j) {
return dp[j] + (sum[i]-sum[j])*p[i] + r[i];
}

int find(int u,int k){
int c = 0;
while(k){
if(k&1) u =  fa[u][c];
k>>=1;
c++;
}
return u;
}
void getMax(int u,int father){
int left = 0,right = num[father]-1;
while(left<right){
int mid = (left+right)/2;
int fa0 = find(father,mid);
int fa1 = fa[fa0][0];

if(g(u,fa0)>g(u,fa1)) left = mid+1;
else right = mid;
}
dp[u] = g(u,find(father,left));
}
int getFa(int u,int father){
int left = 0,right = num[father]-1;
while(left<right){
int mid = (left+right)/2;
int f = find(father,mid);
int ff = fa[f][0];
if((double)f1(ff,f)*f2(f,u)>=(double)f1(f,u)*f2(ff,f)) left = mid+1;
else right = mid;
}
return find(father,left);
}

void dfs(int u,int father){
getMax(u,father);
int tf = getFa(u,father);
fa[u][0] = tf;
num[u] = num[tf]+1;
for(int i=1;(1<<i)<=num[u]-1;i++)
fa[u][i] = find(tf,(1<<i)-1);

for(int i=0;i<e[u].size();i++){
int v = e[u][i];
if(v==father) continue;
sum[v] = sum[u] + f[v];
dfs(v,u);
}
}
int main(){
//    freopen("/home/zyc/Documents/Code/cpp/in","r",stdin);
int T,cas=0;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
e[i].clear();
scanf("%I64d%I64d%I64d",&f[i],&p[i],&r[i]);
//            scanf("%lld%lld%lld",&f[i],&p[i],&r[i]);
}
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
num[0] = 1;
sum[1] = f[1];
dfs(1,0);
ll ans = 0;
for(int i=2;i<=n;i++){
ans += dp[i];
}
printf("Case #%d: %I64d\n",++cas,ans);
//        printf("Case #%d: %lld\n",++cas,ans);
}
return 0;
}