【2022省选模拟】喜欢最最痛——数据结构、凸包、二分

我找不到原题链接

题目描述

题解

答案可以分为两部分：树上的原边、额外边。假设我们要用 $i$ 条额外边，那么一定是选当前可选的最短的 $i$ 条边，所以选的额外边的权值和一定是关于 $i$ 单增的下凸包。

对于树上的原边，如果不加额外边那么代价一定是 $2\ast 边权和$。加一条额外边时，正好可以让树上少走一条简单路径，我们要最小化代价，即是最大化选的路径的长度，所以此时一定是选直径。

加 $i$ 条额外边，正好可以让树上少走 $i$ 条边不重复的简单路径。我们设 $d{p}_i$ 表示选最多 $i$ 条路径时的最大路径长度和，那么凭着做WQS二分时的直觉可以猜到这个 $d{p}_i$ 是个单增的上凸包。既然两部分的答案都是凸包，并且它们加起来也是凸包，所以我们就可以通过二分斜率来找到最小值点。

第二部分的答案可以用平衡树动态维护凸包，然后每次可以直接平衡树上二分一个 $\log$ 求答案。现在问题是怎么快速求每一个 $d{p}_i$。

用树形DP方法显然至少是 $O(n^2)$ 的，我们需要用一个类似求费用流时的反悔退流的方法。当我们选一条路径的时候，我们直接选直径，然后把直径上的边权全部取相反数。第二次选路径的时候，我们还是选直径，此时如果选的直径上有第一次选的边，那么边权被抵消掉，相当于把两条边相交的路径自动处理成了两条边不交的路径。由于证明了每次选择任意路径必定合法，所以每次贪心选直径的正确性也易证。

我们需要支持路径边权翻转，动态维护直径（由于边权不好动态维护，所以下面的做法都是把边权转换成点权做的）。LCT就不说了，我只讲树链剖分的做法。

对于一条直径，它在重链上会交出一段区间。我们只需要维护每个节点走轻儿子能够到达的最远点和距离，然后在重链上做线段树的信息合并。由于要支持翻转边权，所以你要同时维护正边权和负边权情况下的答案。每条重链的答案是独立的，所以最方便且高效的做法是用全局平衡二叉树维护。

但只是这样的话，我们会漏掉走两个轻儿子的路径。当然，我们可以用set维护轻儿子的答案，顺便求走轻儿子的最长路径。但是这样既麻烦又慢，我们可以把边转点过后再三度化，这样每个点最多只有一个轻儿子，可以直接忽略这个情况。

总复杂度可以做到 $O(n\log n)$，但是由于数据结构中维护信息update时的常数非常大（20左右），所以在代码中一些地方写成 $O(n{\log }^{2}n)$ 并不会慢多少。

代码

献上 $O(n\log n)$ 最快代码

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
#pragma GCC optimize("Ofast")
using namespace std;
const int MAXN=400005;
const ll INF=1e17;
inline ll read(){ll x=0;bool f=1;char s=getchar();while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();return f?x:-x;
}
int ptf[50],lpt;
inline void print(ll x,char c='\n'){if(x<0)putchar('-'),x=-x;ptf[lpt=1]=x%10;while(x>9)x/=10,ptf[++lpt]=x%10;while(lpt)putchar(ptf[lpt--]^48);if(c>0)putchar(c);
}
inline ll lowbit(ll x){return x&-x;}struct edge{int v,to;edge(){}edge(int V,int T){v=V,to=T;}
}e[MAXN<<1];
int EN,G[MAXN];
inline void addedge(int u,int v){e[++EN]=edge(v,G[u]),G[u]=EN;e[++EN]=edge(u,G[v]),G[v]=EN;
}
vector<int>G_[MAXN];
int n,k,m;
ll val[MAXN];
inline void pdfs(int x,int fa){//三度化 vector<int>sn;for(int v:G_[x])if(v^fa)pdfs(v,x),sn.push_back(v);if(sn.size()<3){for(int v:sn)addedge(x,v);}else{int o=sn.size()-2;k+=o;for(int i=k;i>k-o+1;i--)addedge(i-1,i);addedge(x,k-o+1),addedge(sn.back(),k),sn.pop_back();for(int i=sn.size()-1,j=k;i>0;i--,j--)addedge(sn[i],j);addedge(x,sn[0]);}
}
int fa[MAXN],dep[MAXN],siz[MAXN],hs[MAXN];
int hd[MAXN],id[MAXN],IN,tl[MAXN],tp[MAXN];
struct node{int u,v;ll d;node(){}node(int U,int V,ll D){u=U,v=V,d=D;}inline bool operator<(const node&b)const{if(d^b.d)return d<b.d;else if(v^b.v) return v<b.v;else return u<b.u;}
}bx[MAXN],as[MAXN];
int fr[MAXN];
ll dr[MAXN];
struct itn{int ls,rs,u,v;ll a,s;node lf[2],rf[2],f[2];bool lz;itn(){}itn(int x,ll A){ls=rs=0,lz=0,s=a=A,u=v=x;f[0]=rf[0]=lf[0]=node(x,fr[x],dr[x]+a);f[1]=rf[1]=lf[1]=node(x,fr[x],dr[x]-a);f[0]=max(f[0],as[x]),f[1]=max(f[1],as[x]);}
}t[MAXN];
int rt[MAXN];
inline void cover(int x){if(!x)return;t[x].a=-t[x].a,t[x].s=-t[x].s;swap(t[x].lf[0],t[x].lf[1]);swap(t[x].rf[0],t[x].rf[1]);swap(t[x].f[0],t[x].f[1]);t[x].lz^=1;
}
inline void pushd(int x){if(t[x].lz)cover(t[x].ls),cover(t[x].rs),t[x].lz=0;
}
inline void update(int x){int ls=t[x].ls,rs=t[x].rs;t[x].u=t[x].v=id[x];if(ls)t[x].u=t[ls].u;if(rs)t[x].v=t[rs].v;int u=t[x].u,v=t[x].v;t[x].s=t[ls].s+t[rs].s+t[x].a;for(int e=0,inv=1;e<2;e++,inv*=-1){node a=t[ls].lf[e],b=t[rs].lf[e];t[x].lf[e]=max(max(a,node(u,b.v,b.d+(t[ls].s+t[x].a)*inv)),node(u,fr[id[x]],(t[ls].s+t[x].a)*inv+dr[id[x]]));a=t[ls].rf[e],b=t[rs].rf[e];t[x].rf[e]=max(max(node(v,a.v,a.d+(t[rs].s+t[x].a)*inv),b),node(v,fr[id[x]],(t[rs].s+t[x].a)*inv+dr[id[x]]));a=t[ls].rf[e],b=t[rs].lf[e];t[x].f[e]=max(max(t[ls].f[e],t[rs].f[e]),max(node(a.v,fr[id[x]],a.d+t[x].a*inv+dr[id[x]]),max(node(fr[id[x]],b.v,b.d+t[x].a*inv+dr[id[x]]),node(a.v,b.v,a.d+b.d+t[x].a*inv) )));t[x].f[e]=max(t[x].f[e],as[id[x]]);}
}
inline void updp(int x,int z){if(!x)return;pushd(x);if(z<x)updp(t[x].ls,z);else if(z>x)updp(t[x].rs,z);update(x);
}
inline void reve(int x,int l,int r,int a,int b){if(!x||l>r)return;if(l>=a&&r<=b){cover(x);return;}pushd(x);if(x>=a&&x<=b)t[x].a=-t[x].a;if(a<x)reve(t[x].ls,l,x-1,a,b);if(b>x)reve(t[x].rs,x+1,r,a,b);update(x);
}
inline void updfr(int x){fr[x]=x,dr[x]=0;if(bx[x].d>dr[x])fr[x]=bx[x].v,dr[x]=bx[x].d;
}
inline void updbx(int x){if((x^tp[x])||!fa[x])return;bx[fa[x]]=t[rt[x]].lf[0];as[fa[x]]=t[rt[x]].f[0];
}
inline int build(int l,int r){if(l>r)return 0;int p=0,s=0,x;for(int i=l;i<=r;i++)s+=siz[id[i]]-siz[hs[id[i]]];for(x=l;x<r;x++){p+=siz[id[x]]-siz[hs[id[x]]];if((p<<1)>s)break;}t[x]=itn(id[x],val[id[x]]);t[x].ls=build(l,x-1),t[x].rs=build(x+1,r);return update(x),x;
}
//prepare end
inline void dfs1(int x){siz[x]=1,dep[x]=dep[fa[x]]+1,hs[x]=0;for(int i=G[x];i;i=e[i].to){int v=e[i].v;if(v==fa[x])continue;fa[v]=x,dfs1(v),siz[x]+=siz[v];if(siz[v]>siz[hs[x]])hs[x]=v;}
}
inline void dfs2(int x){hd[x]=++IN,id[IN]=x,tp[x]=(x==hs[fa[x]]?tp[fa[x]]:x),tl[tp[x]]=IN;fr[x]=x,dr[x]=0,as[x]=bx[x]=node(-1,-1,0);if(hs[x])dfs2(hs[x]);for(int i=G[x];i;i=e[i].to){int v=e[i].v;if(v==fa[x]||v==hs[x])continue;dfs2(v);}if(x==tp[x]){rt[x]=build(hd[x],tl[x]),updbx(x);if(fa[x])updfr(fa[x]);}
}
inline void rev(int u,int v){if(u<1||v<1)return;while(tp[u]^tp[v]){if(dep[tp[u]]<dep[tp[v]])swap(u,v);reve(rt[tp[u]],hd[tp[u]],tl[tp[u]],hd[tp[u]],hd[u]);updbx(tp[u]),u=fa[tp[u]];updfr(u),updp(rt[tp[u]],hd[u]);}if(dep[u]>dep[v])swap(u,v);reve(rt[tp[u]],hd[tp[u]],tl[tp[u]],hd[u],hd[v]);while(fa[tp[u]]){updbx(tp[u]),u=fa[tp[u]];updfr(u),updp(rt[tp[u]],hd[u]);}updbx(tp[u]);
}
ll sum,dp[MAXN],ans[MAXN];
//FHQ begin
mt19937 Rand(835025);
struct fhq{int ls,rs,siz,val;ll a,s;fhq(){}fhq(ll A){ls=rs=0,siz=1,val=Rand(),a=s=A;}
};
#define pii pair<int,int>
#define fi first
#define se second
struct FHQ{fhq t[MAXN];int IN,root;FHQ(){IN=0;}inline void update(int x){t[x].s=t[t[x].ls].s+t[t[x].rs].s+t[x].a;t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+1;}inline pii splitz(int x,ll k){if(!x)return pii(0,0);pii res;if(t[x].a>k)res=splitz(t[x].ls,k),t[x].ls=res.se,update(x),res.se=x;else res=splitz(t[x].rs,k),t[x].rs=res.fi,update(x),res.fi=x;return res;}inline int mergg(int x,int y){if(!x||!y)return x^y;int res=233;if(t[x].val<t[y].val)t[x].rs=mergg(t[x].rs,y),update(x),res=x;else t[y].ls=mergg(x,t[y].ls),update(y),res=y;return res;}inline void insr(ll a){pii x=splitz(root,a);t[++IN]=fhq(a),root=mergg(x.fi,mergg(IN,x.se));}inline ll getmin(int x,int pk){if(!x)return dp[pk];int ds=t[t[x].ls].siz+1;ll cp=t[x].a+dp[pk+ds]-dp[pk+ds-1];if(cp>=0)return getmin(t[x].ls,pk);return t[t[x].ls].s+t[x].a+getmin(t[x].rs,pk+ds);}
}TP;
//FHQ end
signed main()
{freopen("love.in","r",stdin);freopen("love.out","w",stdout);t[0].lf[0]=t[0].lf[1]=t[0].rf[0]=t[0].rf[1]=t[0].f[0]=t[0].f[1]=node(0,0,-INF);n=read(),k=(n<<1)-1,m=read();for(int i=n+1;i<=k;i++){int u=read(),v=read();val[i]=read(),sum+=(val[i]<<1);G_[u].push_back(i),G_[i].push_back(u);G_[v].push_back(i),G_[i].push_back(v);}pdfs(1,0);dfs1(1),dfs2(1),ans[0]=dp[0]=sum;for(int i=1;i<=m;i++){node an=t[rt[1]].f[0];dp[i]=dp[i-1]-an.d,rev(an.u,an.v);}for(int i=1;i<=m;i++)TP.insr(read()),ans[i]=TP.getmin(TP.root,0);for(int i=0;i<=m;i++)print(ans[i],i<m?' ':'\n');return 0;
}