题面

题目背景

因为出题人天天被 ZZH（Zou ZHen） 吊打，所以这场比赛的题目中出现了 ZZH 。

简要题面

数据范围

题解

（笔者写两个log的平衡树和启发式合并卡过的，不足为奇）

首先，很容易看出来n^2的做法是个树形DP，而且不是换根DP（笔者想换根DP想了半小时，发现题读难了，唉），

设 dp[i] 为从 i 出发的答案，容易想到这样的状态转移：

（depth是从1到每个点的距离，即深度，ancestors是每个点的祖先集）

怎么办，j 好像要在 i 的子树中枚举？

但是这个式子好像可以推，我们用斜率优化试试：

这时不妨设  ，那么：

也就是说，对于  的两个决策点 j，k 而言，按照上面的定义把它们抽象成点，若满足上式，则 j 更优，而以下两种情况的 j 肯定不优，可以直接弃掉：

因此，假设这是以 i 为根的子树中的所有点，不包括 i （把它们抽象成点放到平面上）：

我们就要维护这样一个上凸包：

但是呢，这跟朴素的斜率优化不太一样，有以下不同：

1.  无序
2. 新点不一定从两端插入，而有可能从中间插入，这缘于  无序
3. 不一定在序列上跑，而是在树上

第一点其实很好解决，每次从凸包右边开始二分（倍增）就行了。

第二点就有麻烦了，我们得快速在一个凸包内加进一个点。

这种情况，新加的点直接弃掉：

而这种情况两边得分别把下凸的点弃掉：

那就硬枚！左边右边分别找最近的点，判断是否下凸，然后丢掉，再判更远的点……

而这些操作，需要支持区间找前驱后继、找左右端点、区间动态加点删点，

于是乎用平衡树维护。

第三点，相当于每个儿子节点有一棵平衡树，把它们并成一棵大树，用启发式合并。

于是插入O(log)，启发式合并O(nlog^2)，二分（倍增）查找（您就别想平衡树上二分了，太麻烦）O(log^2)，总复杂度 O(nlog^2)

CODE

（可见调试得多么累，但是还是没想到会爆long long）

#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1000005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) ((-x)&(x))
#pragma GCC optimize(2)
LL read() {
    LL f = 1,x = 0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return f * x;
}
const int MOD = 1000000007;
int n,m,i,j,s,o,k;
int a[MAXN],b[MAXN];
//-------------------------------Treap
struct np{int s[2];np(){s[0]=s[1]=0;}np(int A,int B){s[0]=A;s[1]=B;}};
struct tr{
    int s[2];
    int x,siz,hp;
    LL y;
    tr(){x = siz = hp = y = s[0] = s[1] = 0;}
}tre[MAXN];
bool xiatu(int a,int b,int c) {
//    printf("comp %d %d %d\n",a,b,c);
    if(a == 0 || c == 0) return 0;
    if(tre[a].x == tre[b].x && tre[a].y >= tre[b].y) return 1;
    if(tre[c].x == tre[b].x && tre[c].y >= tre[b].y) return 1;
    return ((DB)tre[b].y - tre[a].y) / ((DB)tre[b].x - tre[a].x) <= ((DB)tre[c].y - tre[b].y) / ((DB)tre[c].x - tre[b].x);//就是这儿！写乘法爆了35分
}
int CNT;
int newnode(int xi,LL yi) {
    int x = ++ CNT;tre[x] = tr();
    tre[x].siz = 1;tre[x].hp = rand()*114514ll%MOD;
    tre[x].x = xi;tre[x].y = yi;
    return x;
}
int update(int x) {
    tre[x].siz = tre[tre[x].s[0]].siz + tre[tre[x].s[1]].siz + 1;
    tre[0] = tr();return x;
}
np spli(int x,int xi) {
    np as(0,0);
    if(!x) return as;
    int d = (tre[x].x <= xi);
    as = spli(tre[x].s[d],xi);
    tre[x].s[d] = as.s[!d];
    as.s[!d] = update(x);
    return as;
}
np splil(int x) {
    if(!x) return np();
    if(!tre[x].s[0]) {
        int rp = tre[x].s[1];tre[x].s[1] = 0;
        return np(update(x),rp);
    }
    np as = splil(tre[x].s[0]);
    tre[x].s[0] = as.s[1];
    as.s[1] = update(x);
    return as;
}
np splir(int x) {
    if(!x) return np();
    if(!tre[x].s[1]) {
        int lp = tre[x].s[0];tre[x].s[0] = 0;
        return np(lp,update(x));
    }
    np as = splir(tre[x].s[1]);
    tre[x].s[1] = as.s[0];
    as.s[0] = update(x);
    return as;
}
int findp(int x,int rk) {
    if(!x) return 0;
    if(tre[tre[x].s[0]].siz+1 == rk) return x;
    if(tre[tre[x].s[0]].siz+1 < rk)
        return findp(tre[x].s[1],rk - tre[tre[x].s[0]].siz - 1);
    return findp(tre[x].s[0],rk);
}
int merg(int p1,int p2) {
    if(!p1) return p2;if(!p2) return p1;
    if(tre[p1].hp < tre[p2].hp) {
        tre[p1].s[1] = merg(tre[p1].s[1],p2);return update(p1);
    }
    tre[p2].s[0] = merg(p1,tre[p2].s[0]);return update(p2);
}
int ins(int x,int y) {
//    printf("(%d)ins:(%d,%lld)\n",x,tre[y].x,tre[y].y);
    if(!x) return y;
    np p = spli(x,tre[y].x);
    np lp = splir(p.s[0]),rp = splil(p.s[1]);
//    printf("%d) (%d\n",lp.s[1],rp.s[0]);
    if(xiatu(lp.s[1],y,rp.s[0])) return merg(merg(lp.s[0],lp.s[1]),merg(rp.s[0],rp.s[1]));
    np llp = splir(lp.s[0]);
    while(xiatu(llp.s[1],lp.s[1],y)) {
        lp = llp;llp = splir(lp.s[0]);
    }lp.s[0] = merg(llp.s[0],llp.s[1]);p.s[0] = merg(lp.s[0],lp.s[1]);
    np rrp = splil(rp.s[1]);
//        printf("ok1\n");
    while(xiatu(y,rp.s[0],rrp.s[0])) {
//        printf("ok2\n");
        rp = rrp;rrp = splil(rp.s[1]);
    }
    rp.s[1] = merg(rrp.s[0],rrp.s[1]);p.s[1] = merg(rp.s[0],rp.s[1]);
//    printf("OK(%d,%d,%d)\n",tre[p.s[0]].siz,tre[y].siz,tre[p.s[1]].siz);
    return merg(merg(p.s[0],y),p.s[1]);
}
int st[MAXN],tp;
void distr(int x) {
    if(!x) return ;
    distr(tre[x].s[0]);distr(tre[x].s[1]);
    tre[x].s[0] = tre[x].s[1] = 0;
    st[++ tp] = update(x);
    return ;
}
bool pb(int a,int b,LL nm) {
    return (tre[b].y - tre[a].y) < (tre[b].x - tre[a].x) *1ll* nm;
}
//------------------------------------
struct it{
    int v,w;
    it(){v=w=0;}
    it(int V,int W){v=V;w=W;}
};
vector<it> g[MAXN];
LL dp1[MAXN],d[MAXN];
int f[MAXN],ed[MAXN],rt[MAXN];
int bing(int ra,int rb) {
    if(tre[ra].siz > tre[rb].siz) swap(ra,rb);
    tp = 0;
    distr(ra);
    for(int i = 1;i <= tp;i ++) rb = ins(rb,st[i]);
    return rb;
}
void dfs(int x,int fa,int fe) {
    dp1[x] = 0; d[x] = d[f[x] = fa] + (ed[x] = fe);
    rt[x] = 0;
    for(int i = 0;i < (int)g[x].size();i ++) {
        int y = g[x][i].v,w = g[x][i].w;
        if(y != fa) {
            dfs(y,x,w);
            rt[x] = bing(rt[x],rt[y]);
//            printf("%d -> %d\n",x,y);
//            print(rt[x]);
//            ENDL;
        }
    }
    int ad = tre[rt[x]].siz;
    for(int i = 20;i >= 0;i --) {
        if(ad-(1<<i) > 0 && pb(findp(rt[x],ad-(1<<i)),findp(rt[x],ad-(1<<i)+1),-1ll*(a[x] + d[x]))) {
            ad -= (1<<i);
        }
    }
    ad = findp(rt[x],ad);
    dp1[x] = max(dp1[x],(a[x] + d[x]) *1ll* tre[ad].x + tre[ad].y);
    LL Y = dp1[x] - d[x] *1ll* b[x];
    rt[x] = ins(rt[x],newnode(b[x],Y));
    return ;
}
int main() {
    freopen("journey.in","r",stdin);
    freopen("journey.out","w",stdout);
    n = read();
    for(int i = 1;i <= n;i ++) a[i] = read(),b[i] = read();
    for(int i = 1;i < n;i ++) {
        s = read();o = read();k = read();
        g[s].push_back(it(o,k));
        g[o].push_back(it(s,k));
    }
    dfs(1,0,0);
    for(int i = 1;i <= n;i ++) {
        printf("%lld\n",dp1[i]);
    }
    return 0;
}