本文共 5024 字，大约阅读时间需要 16 分钟。

题面

题目背景

因为出题人天天被 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
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         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];//-------------------------------Treapstruct 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
         
           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<
          
            0 && pb(findp(rt[x],ad-(1<
           
            <
            
             <= 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;}
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43960414/article/details/110441048 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！