牛客18多校第一场H
牛客18多校第一场H
此文更新于2019.7.12
给一颗边带权点不带权点树
定义两点间的距离为:
若路径上的边权构成数列a[0...n]
则距离d= 对所有i>=1求和 (a[i-1]-a[i])*(a[i-1]-a[i])
现在要求距离每个点最远的那个点的距离为多少
定义两点间的距离为:
若路径上的边权构成数列a[0...n]
则距离d= 对所有i>=1求和 (a[i-1]-a[i])*(a[i-1]-a[i])
现在要求距离每个点最远的那个点的距离为多少
树dp求down很简单
关于up , 仔细分析,抽象出来为此:
给你w[]和d[]
对每一个i,要求出最大化j!=i时的d[j]+(w[i]-w[j])
化简后发现为
d[j]+w[i]*w[i]+w[j]*w[j]-2*w[i]*w[j]
= w[i]*w[i] + (-2*w[i])*w[j] + (d[j]+w[j]*w[j])
显然斜率优化,我们排序后对前缀和后缀做两遍斜率优化即可
关于up , 仔细分析,抽象出来为此:
给你w[]和d[]
对每一个i,要求出最大化j!=i时的d[j]+(w[i]-w[j])
化简后发现为
d[j]+w[i]*w[i]+w[j]*w[j]-2*w[i]*w[j]
= w[i]*w[i] + (-2*w[i])*w[j] + (d[j]+w[j]*w[j])
显然斜率优化,我们排序后对前缀和后缀做两遍斜率优化即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pwx2(x) ((x)*(x))
const ll maxn=1e5+5;
struct star{ll v,w,nex;}edge[maxn<<1];
ll head[maxn],cnt,n;
ll down[maxn],up[maxn],ans[maxn];
struct line{ll k,b,id;};// y=kx+b
double cross(line l1,line l2){// k1x+b1=k2x+b2 -> k1x-k2x=b2-b1
return -double(l1.b-l2.b)/(l1.k-l2.k);
}
ll val_at(line l1,ll x){
return x*l1.k+l1.b;
}
void ini(ll _n){
n=_n;
cnt=-1;
for(ll i=0;i<=n;i++) head[i]=-1,down[i]=up[i]=ans[i]=0;
}
void add_edge(ll u,ll v,ll w){
edge[++cnt]=star{v,w,head[u]}; head[u]=cnt;
edge[++cnt]=star{u,w,head[v]}; head[v]=cnt;
}
void dfs1(ll u,ll father=0,ll w=0){
for(ll i=head[u];~i;i=edge[i].nex){
if(edge[i].v==father) continue;
dfs1(edge[i].v,u,edge[i].w);
if(father) {
down[u]=max(down[u],down[edge[i].v]+pwx2(w-edge[i].w));
ans[father]=max(ans[father],down[u]);
}
}
}
void dfs2(ll u,ll father=0){
vector<line> vec;
for(ll i=head[u];~i;i=edge[i].nex){
ll v=edge[i].v,w=edge[i].w;
if(v==father) vec.push_back(line{-2*w,up[u]+w*w,i});
else vec.push_back(line{-2*w,down[v]+w*w,i});
}
sort(vec.begin(),vec.end(),[](line l,line r){return l.k<r.k;});
static line stk[maxn];
ll tot=0;
for(ll i=0;i<vec.size();i++){// k++ x--
star&e=edge[vec[i].id];
while(tot>=2&&cross(stk[tot],stk[tot-1])>e.w)tot--;
if(e.v!=father&&tot>=1) {
star&e2=edge[stk[tot].id];
up[e.v]=max(up[e.v],val_at(stk[tot],e.w)+e.w*e.w);
ans[e.v]=max(ans[e.v],up[e.v]);
}
if(tot>=1&&vec[i].k==stk[tot].k){
if(vec[i].b>stk[tot].b)tot--;
else continue;
}
while(tot>=2&&cross(vec[i],stk[tot])<cross(stk[tot],stk[tot-1]))tot--;
stk[++tot]=vec[i];
}
tot=0;
for(ll i=int(vec.size())-1;i>=0;i--){// k--
star&e=edge[vec[i].id];
while(tot>=2&&cross(stk[tot],stk[tot-1])<e.w)tot--;
if(e.v!=father&&tot>=1) {
star&e2=edge[stk[tot].id];
up[e.v]=max(up[e.v],val_at(stk[tot],e.w)+e.w*e.w);
ans[e.v]=max(ans[e.v],up[e.v]);
}
if(tot>=1&&vec[i].k==stk[tot].k){
if(vec[i].b>stk[tot].b)tot--;
else continue;
}
while(tot>=2&&cross(vec[i],stk[tot])>cross(stk[tot],stk[tot-1]))tot--;
stk[++tot]=vec[i];
}
for(ll i=head[u];~i;i=edge[i].nex){
if(edge[i].v==father) continue;
dfs2(edge[i].v,u);
}
}
int main(){
ll n;
while(~scanf("%lld",&n)){
ini(n);
for(ll i=0;i<n-1;i++){
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add_edge(u,v,w);
}
dfs1(1);
dfs2(1);
for(ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
}
}
此文标签using namespace std;
typedef long long ll;
#define pwx2(x) ((x)*(x))
const ll maxn=1e5+5;
struct star{ll v,w,nex;}edge[maxn<<1];
ll head[maxn],cnt,n;
ll down[maxn],up[maxn],ans[maxn];
struct line{ll k,b,id;};// y=kx+b
double cross(line l1,line l2){// k1x+b1=k2x+b2 -> k1x-k2x=b2-b1
return -double(l1.b-l2.b)/(l1.k-l2.k);
}
ll val_at(line l1,ll x){
return x*l1.k+l1.b;
}
void ini(ll _n){
n=_n;
cnt=-1;
for(ll i=0;i<=n;i++) head[i]=-1,down[i]=up[i]=ans[i]=0;
}
void add_edge(ll u,ll v,ll w){
edge[++cnt]=star{v,w,head[u]}; head[u]=cnt;
edge[++cnt]=star{u,w,head[v]}; head[v]=cnt;
}
void dfs1(ll u,ll father=0,ll w=0){
for(ll i=head[u];~i;i=edge[i].nex){
if(edge[i].v==father) continue;
dfs1(edge[i].v,u,edge[i].w);
if(father) {
down[u]=max(down[u],down[edge[i].v]+pwx2(w-edge[i].w));
ans[father]=max(ans[father],down[u]);
}
}
}
void dfs2(ll u,ll father=0){
vector<line> vec;
for(ll i=head[u];~i;i=edge[i].nex){
ll v=edge[i].v,w=edge[i].w;
if(v==father) vec.push_back(line{-2*w,up[u]+w*w,i});
else vec.push_back(line{-2*w,down[v]+w*w,i});
}
sort(vec.begin(),vec.end(),[](line l,line r){return l.k<r.k;});
static line stk[maxn];
ll tot=0;
for(ll i=0;i<vec.size();i++){// k++ x--
star&e=edge[vec[i].id];
while(tot>=2&&cross(stk[tot],stk[tot-1])>e.w)tot--;
if(e.v!=father&&tot>=1) {
star&e2=edge[stk[tot].id];
up[e.v]=max(up[e.v],val_at(stk[tot],e.w)+e.w*e.w);
ans[e.v]=max(ans[e.v],up[e.v]);
}
if(tot>=1&&vec[i].k==stk[tot].k){
if(vec[i].b>stk[tot].b)tot--;
else continue;
}
while(tot>=2&&cross(vec[i],stk[tot])<cross(stk[tot],stk[tot-1]))tot--;
stk[++tot]=vec[i];
}
tot=0;
for(ll i=int(vec.size())-1;i>=0;i--){// k--
star&e=edge[vec[i].id];
while(tot>=2&&cross(stk[tot],stk[tot-1])<e.w)tot--;
if(e.v!=father&&tot>=1) {
star&e2=edge[stk[tot].id];
up[e.v]=max(up[e.v],val_at(stk[tot],e.w)+e.w*e.w);
ans[e.v]=max(ans[e.v],up[e.v]);
}
if(tot>=1&&vec[i].k==stk[tot].k){
if(vec[i].b>stk[tot].b)tot--;
else continue;
}
while(tot>=2&&cross(vec[i],stk[tot])>cross(stk[tot],stk[tot-1]))tot--;
stk[++tot]=vec[i];
}
for(ll i=head[u];~i;i=edge[i].nex){
if(edge[i].v==father) continue;
dfs2(edge[i].v,u);
}
}
int main(){
ll n;
while(~scanf("%lld",&n)){
ini(n);
for(ll i=0;i<n-1;i++){
ll u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
add_edge(u,v,w);
}
dfs1(1);
dfs2(1);
for(ll i=1;i<=n;i++) printf("%lld\n",ans[i]);
}
}
树形dp 斜率优化dp
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Believe it!