【bzoj1758】[Wc2010]重建计划 二分答案+单调队列+点分治

首先二分答案ans，每条边权值减去ans，问题转化成整棵树中长度在[L,U]之间，权值和最大的路径是否大于0.

点分治

考虑如何求出经过根的所有路径对答案的影响，

枚举根的每个儿子，

g[i]表示当前子树中深度为i的节点的最大权值和

f[i]表示之前的子树中深度为i的节点的最大权值和

枚举i，查询f[L-i]~f[U-i]之间的最大值，这个可以用线段树来做，复杂度是O(∑size log n)的

但是，题解上说用单调队列来做，因为随着i的增大，询问区间是单调向左平移的。

但是这样的复杂度好像是不对的

比如，一棵树，根节点有10^5个深度为1的儿子，还有1个深度为10^5的儿子是一条链，这样的话每次枚举都会把深度为10^5的那条链重新计算一遍，所以复杂度会变成O(n^2)

写这道题的时候感觉不太对，晨神hack了一下，果然有问题，不过既然已经写了单调队列，那就将错就错吧。

写的时候，每次要做完整个儿子，再更新f数组，因为这个错误调了好久。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#define maxn 100010
#define inf 1e15
#define eps 1e-5

using namespace std;

int head[maxn],to[maxn*2],next[2*maxn],fa[maxn],size[maxn];
double dep[maxn],f[maxn],g[maxn],len[2*maxn];
int q[maxn];
bool vis[maxn];
int n,m,num,L,U,l,r;
double Ans,ans,mid,sum;

void addedge(int x,int y,double z)
{
num++;to[num]=y;len[num]=z;next[num]=head[x];head[x]=num;
}

void get_root(int x,int Size,int &cg)
{
bool flag=1;
size[x]=1;
for (int p=head[x];p;p=next[p])
  if (!vis[to[p]] && to[p]!=fa[x])
  {
  fa[to[p]]=x;
  get_root(to[p],Size,cg);
  size[x]+=size[to[p]];
  if (size[to[p]]>Size/2) flag=0; 
  }
if (Size-size[x]>Size/2) flag=0;
if (flag) cg=x;
}

void dfs1(int x)
{
for (int p=head[x];p;p=next[p])
  if (!vis[to[p]] && to[p]!=fa[x]) fa[to[p]]=x,dfs1(to[p]); 
} 

void dfs2(int x,int d,int &mx)
{
mx=max(mx,d);
g[d]=max(g[d],dep[x]);
for (int p=head[x];p;p=next[p])
  if (to[p]!=fa[x] && !vis[to[p]])
  {
  dep[to[p]]=dep[x]+len[p]-mid;
  dfs2(to[p],d+1,mx);
  }
}

void calc(int x)
{
f[0]=0.0;dep[x]=0.0;
int mx=0;
for (int p=head[x];p;p=next[p])
  if (to[p]!=fa[x] && !vis[to[p]])
  {
  int dp=0;
  dep[to[p]]=dep[x]+len[p]-mid;
  dfs2(to[p],1,dp);
mx=max(mx,dp);
  int j=mx;
  l=1,r=0;
  for (int i=1;i<=dp;i++)
  {
  while (j>=0 && i+j>=L)
  {
  while (l<=r && f[q[r]]<f[j]) q[r--]=0; 
  q[++r]=j--;
  }
  while (l<=r && q[l]+i>U) q[l++]=0;
  if (l<=r && L<=i+q[l] && i+q[l]<=U) ans=max(ans,g[i]+f[q[l]]);
  }
  for (int i=1;i<=dp;i++) f[i]=max(f[i],g[i]),g[i]=-inf;
  }
for (int i=1;i<=mx;i++) f[i]=-inf;
}

void solve(int x,int Size)
{
if (Size<=L) return;
int cg;
fa[x]=0;
get_root(x,Size,cg);
size[fa[cg]]=Size-size[cg];
fa[cg]=0;vis[cg]=1;
dfs1(cg);
double l=0.0,r=1000000.0;
while (r-l>eps)
{
mid=(l+r)/2.0;
ans=-1;calc(cg);
if (ans>=0) l=mid; else r=mid;
}
Ans=max(Ans,l);
for (int p=head[cg];p;p=next[p]) if (!vis[to[p]]) solve(to[p],size[to[p]]);
}

int main()
{
scanf("%d",&n);
scanf("%d%d",&L,&U);
for (int i=1;i<n;i++)
{
int x,y;
double z;
scanf("%d%d%lf",&x,&y,&z);
addedge(x,y,z);addedge(y,x,z);
}
Ans=0.0;
for (int i=1;i<=n;i++) f[i]=g[i]=-inf;
solve(1,n);
printf("%.3lf\n",Ans);
return 0;
}