wordpress站点收录好,天津网络推广公司,网站制作模板北京,网站命名方式正题
题面链接:https://www.luogu.com.cn/problem/CF932F 题目大意 nnn个点的一棵树#xff0c;从xxx跳到yyy#xff08;要求yyy在xxx的子树中#xff09;会产生Ax∗ByA_x*B_yAx∗By的代价#xff0c;求每个节点出发跳到某个叶节点的最小代价。 解题思路
考虑dpdpdp的…正题
题面链接:https://www.luogu.com.cn/problem/CF932F 题目大意
nnn个点的一棵树从xxx跳到yyy要求yyy在xxx的子树中会产生Ax∗ByA_x*B_yAx∗By的代价求每个节点出发跳到某个叶节点的最小代价。 解题思路
考虑dpdpdp的话那么有fxfyAx∗Byf_xf_yA_x*B_yfxfyAx∗By这个式子可以考虑斜率优化若y1y_1y1比y2y_2y2优那么有fy1−fy2By1−By2≥Ax\frac{f_{y_1}-f_{y_2}}{B_{y_1}-B_{y_2}}\geq A_xBy1−By2fy1−fy2≥Ax 也就是我们对于每个节点要维护一个子树里所有点构成的一个下凸壳。
考虑树上启发式合并CDQCDQCDQ我们要求一个序列使得被贡献的点排在贡献点的后面。维护一个序列每次我们保留重子树的序列然后再加入其它轻子树的序列当到一个节点的头顶上是一条轻边时我们就对这个序列跑一次CDQCDQCDQ来维护凸壳然后清空序列。需要注意的是对于二次扫描轻子树的节点需要标记不能在CDQCDQCDQ分治中被修改答案。
时间复杂度O(nlog2n)O(n\log^2 n)O(nlog2n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
#define ll long long
using namespace std;
const ll N1e510;
struct node{ll to,next;
}e[N*2];
ll n,tot,ls[N],a[N],b[N],f[N],siz[N],son[N];
ll cnt,q[N],p[N],v[N],st[N],rfn[N];
void addl(ll x,ll y){e[tot].toy;e[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){siz[x]1;for(ll ils[x];i;ie[i].next){ll ye[i].to;if(yfa)continue;dfs(y,x);siz[x]siz[y];if(siz[y]siz[son[x]])son[x]y;}return;
}
bool cmp(ll x,ll y)
{return a[x]a[y];}
bool cMp(ll x,ll y)
{return (b[x]b[y])?(f[x]f[y]):(b[x]b[y]);}
double slope(ll x,ll y)
{return (double)(f[x]-f[y])/(b[x]-b[y]);}
void cdq(ll l,ll r){if(lr)return;ll mid(lr)1,cnt1l-1,cnt2mid;for(ll il;ir;i)if(rfn[p[i]]mid)q[cnt1]p[i];else q[cnt2]p[i];for(ll il;ir;i)p[i]q[i];cdq(l,mid);ll tot0;for(ll il;imid;i){if(b[p[i]]b[p[i-1]]i!l)continue;while(tot1slope(st[tot-1],st[tot])slope(st[tot-1],p[i]))tot--;st[tot]p[i];}for(ll imid1;ir;i){if(v[p[i]])continue;while(tot1slope(st[tot-1],st[tot])-a[p[i]])tot--;ll xp[i],yst[tot];f[x]min(f[x],f[y]a[x]*b[y]);}cdq(mid1,r);sort(pl,p1r,cMp);return;
}
void calc(ll x,ll fa){p[cnt]x;rfn[x]cnt;v[x]1;for(ll ils[x];i;ie[i].next){ll ye[i].to;if(yfa)continue;calc(y,x);}
}
void solve(ll x,ll fa,ll top){for(ll ils[x];i;ie[i].next){ll ye[i].to;if(yfa||yson[x])continue;solve(y,x,y);}if(son[x])solve(son[x],x,top);else f[x]0;for(ll ils[x];i;ie[i].next){ll ye[i].to;if(yfa||yson[x])continue;calc(y,x);}p[cnt]x;rfn[x]cnt;v[x](!son[x]);if(xtop){sort(p1,p1cnt,cmp);cdq(1,cnt);cnt0;}return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i)scanf(%lld,a[i]);for(ll i1;in;i)scanf(%lld,b[i]);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}memset(f,0x3f,sizeof(f));dfs(1,1);solve(1,1,1);for(ll i1;in;i)printf(%lld\n,f[i]);return 0;
}
