[DS记录]P4292 [WC2010]重建计划
command_block
·
·
个人记录
看了看去年的代码发现看不懂,于重写一遍题解。
题意 : 给出一棵带权树,要求选出一条边数在[L,R]内的路径,使得边权平均值最大。
------------
首先$01$分数规划,问题就被转化为了 : 判定树上是否存在边数在$[L,R]$内,且边权和大于$0$的路径。
一个选择是点分治,不过常数大,而且需要额外的数据结构维护做到严格单次$O(n\log n)$,所以不好写。
另一个选择是长链剖分,由于需要区间询问,使用线段树来辅助。
设$f[u][len]$为点$u$向下延伸$len$条边后能得到的边权和最大的路径。
根据长链剖分的结论,每次暴力合并轻链头(在线段树上单点修改),复杂度是正确的。
合并的同时顺手查询上下绕行的答案。还要在每个点处统计直下的路径。
接下来考虑如何继承长链。
可以在线段树上按下标分配这些长链的空间,继承的时候多了一条边,相当于区间加法。
我们可以不去搞加法标记,而是考虑这些标记的影响,相当于“树外标记永久化”。不过我们插入的东西需要减去标记的贡献。
具体的来讲,我们发现在点$u$处的加法标记和为 : $u$沿着长链到底端的权值和。
观察到`DP`值总是在变大,我们可以在修改时减少一点常数。
```cpp
#include<cstdio>
#include<vector>
#define ll long long
#define db double
#define pb push_back
#define MaxN 100500
using namespace std;
inline int read(){
register int X=0;
register char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
int n,L,R;
db a[MaxN<<2],wfc;
void build(int l=1,int r=n,int u=1)
{
a[u]=-1e16;
if (l==r)return ;
int mid=(l+r)>>1;
build(l,mid,u<<1);
build(mid+1,r,u<<1|1);
}
int to;
void chg(int l=1,int r=n,int u=1)
{
a[u]=max(a[u],wfc);
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
}
int wfl,wfr;
db qry(int l=1,int r=n,int u=1)
{
if (wfl<=l&&r<=wfr)return a[u];
int mid=(l+r)>>1;db ans=-1e16;
if (wfl<=mid)ans=qry(l,mid,u<<1);
if (mid<wfr)ans=max(ans,qry(mid+1,r,u<<1|1));
return ans;
}
vector<int> g[MaxN],l[MaxN];
int son[MaxN],len[MaxN];
ll _tag[MaxN];db tag[MaxN];
void pfs(int u,int fa)
{
int slen;
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
pfs(v,u);
if (len[v]>len[son[u]]){
son[u]=v;
slen=l[u][i];
}
}
if (son[u]){
len[u]=len[son[u]]+1;
_tag[u]=_tag[son[u]]+slen;
}
}
int p[MaxN],id;
db *f[MaxN],t[MaxN],ans,mid;
void dfs(int u,int fa)
{
wfc=f[u][0]=-tag[u];
to=p[u];chg();
if (son[u]){
f[son[u]]=f[u]+1;
p[son[u]]=p[u]+1;
dfs(son[u],u);
}
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa&&v!=son[u]){
f[v]=t+(p[v]=id);id+=len[v]+1;
dfs(v,u);
db pc=(l[u][i]-mid)+tag[v];
for (int j=0;j<=len[v];j++){
wfl=p[u]+max(L-j-1,0);
wfr=p[u]+min(R-j-1,len[u]);
if (wfl<=wfr){
wfc=f[v][j]+pc;
ans=max(ans,wfc+qry()+tag[u]);
}
}pc-=tag[u];
for (int j=0;j<=len[v];j++){
wfc=f[v][j]+pc;
if (wfc>f[u][j+1]){
f[u][j+1]=wfc;
to=p[u]+j+1;
chg();
}
}
}
wfl=p[u]+L;wfr=p[u]+min(R,len[u]);
if (wfl<=wfr)ans=max(ans,qry()+tag[u]);
}
bool check()
{
for (int i=1;i<=n;i++)
tag[i]=1.00*_tag[i]-len[i]*mid;
build();ans=-1e16;
f[1]=t+(p[1]=id=1);id+=len[1]+1;
dfs(1,0);
return ans>-1e-8;
}
int main()
{
n=read();L=read();R=read();
for(int i=1,f,t,len;i<n;i++){
f=read();t=read();len=read();
g[f].pb(t);l[f].pb(len);
g[t].pb(f);l[t].pb(len);
}len[0]=-1;pfs(1,0);
db l=0,r=1e6;
while(r-l>1e-4){
mid=(l+r)/2;
if (check())l=mid;
else r=mid;
}printf("%.3lf",l);
return 0;
}
```