个人可以做下载类网站吗,wordpress 突然加速,wordpress的mysql扩展,小程序定制公司哪里有解析
感觉是左偏树的神题了.
首先有一个比较显然的结论#xff0c;一个合法的方案中#xff0c;两个叶子到它们 lca\text{lca}lca 的距离必须相等.
考虑设计 dp\text{dp}dp #xff1a; fi,xf_{i,x}fi,x 表示 iii 的子树中#xff0c;所有叶子到它的距离为 xxx 的最小…解析
感觉是左偏树的神题了.
首先有一个比较显然的结论一个合法的方案中两个叶子到它们 lca\text{lca}lca 的距离必须相等.
考虑设计 dp\text{dp}dp
fi,xf_{i,x}fi,x 表示 iii 的子树中所有叶子到它的距离为 xxx 的最小代价.
考虑这个函数如何向父亲合并. 设一个结点到父亲的距离为 cic_ici . 朴素 dp\text{dp}dp 就有 fi,x∑j∈soniminv≥0xfj,x−v∣cj−v∣f_{i,x}\sum_{j\in son_i}\min_{v\geq0}^xf_{j,x-v}|c_j-v|fi,xj∈soni∑v≥0minxfj,x−v∣cj−v∣ 这玩意显然复杂度爆炸啊…
换个角度考虑 fff 函数本身的性质. 不难想到原来的函数应该是一个下凸的线性函数. sonison_isoni 的函数如何向 iii 合并 一开始这个函数似乎就是简单的所有子节点函数相加合成. 并且由于 cic_{i}ci 的存在这个函数肯定要往右移 cic_ici . 假设移动完长这样 但是考虑到有 iii 连向 faifa_ifai 的边有些修改可以在这里一起改就不必各自麻烦了所以肯定函数会变化准确的说变得更好.
设斜率为 000 的区间为 [L,R][L,R][L,R] . 然后我们发现 RRR 右侧还有好多斜率大于 111 的地方. 大概的实际意义就是每个儿子都各自修改. 这就很亏. 所以对于 fi,xf_{i,x}fi,x 我们干脆在先全部调整成距离为 RRR支付 fi,Rf_{i,R}fi,R 的代价再把当前结点连向父亲的边权值增大 x−Rx-Rx−R . 这样就把 RRR 右侧的斜率全都变成了 111 . 变成这样
另一边可以类似的搞吗 差不多但是有个问题… 边的权值非负 所以我们斜率为 111 的区间往左增加的长度最多为 cic_ici . 后面的函数就往左顺延 cic_ici . 也就是变成
别忘了本来这个函数是整体右移 cic_ici . 这里左边的斜率大于1的区间又往左移动了 cic_ici . 所以其实根本位置没变.
总结一下的话这个函数合并到父亲后就是 把斜率为 000 的区间 [L,R][L,R][L,R] 右移 cic_ici 把 RRR 右边的函数斜率全改为 111 斜率为 −1-1−1 的区间往右延长 cic_ici 补上 LLL 右移的空缺. 实现上建一个可并堆维护所有的拐点令相邻拐点斜率差为 111 如果两端之间斜率差大于 111 就插多个横坐标相同的拐点那么其实就把 RRR 右侧的所有拐点弹掉并把 LLL 和 RRR 的坐标加上 cic_ici 就行了.
最后合并到根之后我们只有拐点的横坐标如何求出答案也就是 f1,Lf_{1,L}f1,L 呢 注意到 f1,0f_{1,0}f1,0 其实就是所有边权之和能很方便的求出来又因为我们知道相邻两个端点的斜率差均为 111 [L,R][L,R][L,R] 的斜率为 000 那么我们只需要倒着推一遍就行了.
代码
#includebits/stdc.h
const int N1e6100;
const int mod1e97;
#define ll long long
using namespace std;
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m;
int fa[N],fv[N],son[N];
int rt[N],tot,ls[N],rs[N],dis[N];
ll val[N];
int merge(int x,int y){//printf(merge x%d y%d\n,x,y);if(!x||!y) return x|y;if(val[x]val[y]) swap(x,y);rs[x]merge(rs[x],y);if(dis[ls[x]]dis[rs[x]]) swap(ls[x],rs[x]);dis[x]dis[rs[x]]1;return x;
}
inline int pop(int x){return merge(ls[x],rs[x]);
}
ll sum;
void debug(int x){if(!x) return;printf(x%d ls%d rs%d val%lld\n,x,ls[x],rs[x],val[x]);debug(ls[x]);debug(rs[x]);return;
}
int main(){dis[0]-1;nread();mread();for(int i2;inm;i){fa[i]read();son[fa[i]];sum(fv[i]read());}for(int inm;i2;i--){ll l(0),r(0);//printf(i%d\n,i);if(in){while(--son[i]) rt[i]pop(rt[i]);rval[rt[i]];rt[i]pop(rt[i]);lval[rt[i]];rt[i]pop(rt[i]);//printf(ok);}val[tot]lfv[i];val[tot]rfv[i];rt[i]merge(rt[i],merge(tot-1,tot));//printf(OK rtfa%d\n,rt[fa[i]]);printf(\ni%d:\n,i);debug(rt[i]);rt[fa[i]]merge(rt[fa[i]],rt[i]);}//debug(rt[1]);while(son[1]--){rt[1]pop(rt[1]);//printf(\nrt%d\n,rt[1]);}while(rt[1]){sum-val[rt[1]];rt[1]pop(rt[1]);//printf(\nrt%d\n,rt[1]);}printf(%lld\n,sum);
}
/*
1
281239
*/
