树的点分治 bzoj1758【WC2010】重建计划

本文主要是介绍树的点分治 bzoj1758【WC2010】重建计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
给定一颗树，找到一条路径长度大于等于L，小于等于U。
求满足条件的最大路径平均权值。

题目分析:（树的点分治）
树的点分治入门传送门

上网看了不少题解，路子大致都是：二分+树的点分治+单调队列。
恩恩，道理都懂，但是你不告诉宝宝每一步怎么做像宝宝这种蒟蒻怎么知道怎么写啊掀桌(╯‵□′)╯︵┻━┻，现在写题解的人怎么都这么懒呢QAQ
后来回去看看自己写的其他题解，也都是会的人看了就懂，不会的人看了还是不会，跟没写一样╮(╯ _ ╰)╭好吧那上一段话就当我没说O(∩_∩)O

首先看到所求为一些路径权值的平均数，但是在树分治并不资磁除法，所以可以考虑二分答案。把所有的边权减去二分出来的答案，作为当前边权，检验是否有一个合法的路径满足权值和大于0即可。

检验答案的时候，对于每一分治的根节点，顺序处理它的所有子树，然后合并子树信息。
我们需要维护一个数组代表已搜过的子树中深度为i时的最大权值。
然后对于一个新加入的子树，先搜出这个子树中深度为i时的最大权值，然后和之前的搜过的子树拼接一下，看能拼出来的最大值是否大于等于0。
但是由于路径长度是有范围的，我们可以用一个单调队列维护。

我使用的方法是：
把已经搜过的子树中的点放入单调队列中维护，按照深度从大到小的顺序往里面放。
然后把当前搜索的子树按照深度从小到大扫描一遍，扫到每个点时，判断队列中的深度是否合法，如果队首不合法就弹掉，如果能继续加深度更小的点就加进来，然后更新答案，满足大于等于0的话就直接返回true即可。

还可以考虑一些优化（据说这题卡常？）
每次存最优值的数组不要memset，这个东西常数大，每次用了什么就还原什么。

如果你收到深度大于U的位置就不需要再向下搜了，因为不可能更新答案。

这道题因为要二分，所以可能要做很多次树分治，这样的话我们可以先处理出一个树的重心的序列。然后每次就直接按照这个序列分治就可以。
当然你也可以把二分套在树分治里，这样就不存在这个问题了，但是做法可能会不太一样。

还有一些其他的优化（但是我都没有用=。=），比如说如果分治的点数小于L就不用分了直接返回什么的……

代码如下:

#include <cstdio>
#define N 120000
#define INF 2147483647
using namespace std;
const double EPS=1e-6;
inline double Max(double x,double y) { return x>y?x:y; }
inline int Max(int x,int y) { return x>y?x:y; }
int n,root,sum,rf,L,U;
double l,r,mid;
int fir[N],nes[N<<1],v[N<<1],tot=1;
int xl[N],sz[N],son[N],top;
int dep[N],dl[N];
int maxn;
bool vis[N];
double q[N<<1],dis[N],f[N],fx[N];
void read(int &n)
{n=0;static char ch;while(~(ch=getchar()) && (ch>'9' || ch<'0'));n=ch-'0';while(~(ch=getchar()) && ch<='9' && ch>='0') n=(n<<1)+(n<<3)+(ch-'0');return;
}
void edge(int x,int y,int z)
{tot++;v[tot]=y;q[tot]=(double)z;nes[tot]=fir[x];fir[x]=tot;return;
}
#define edge(x,y,z) edge(x,y,z),edge(y,x,z)
void find_focus(int c,int fa)
{sz[c]=1; son[c]=0;for(int t=fir[c];t;t=nes[t]){if(v[t]==fa || vis[v[t]]) continue;find_focus(v[t],c);sz[c]+=sz[v[t]];if(sz[v[t]]>son[c]) son[c]=sz[v[t]];}if(sum-sz[c]>son[c]) son[c]=sum-sz[c];if(son[c]<son[root]) root=c,rf=fa;return;
}
void get_xl(int c)
{xl[++top]=c; vis[c]=true;for(int t=fir[c];t;t=nes[t]){if(vis[v[t]]) continue;root=0; sum=sz[v[t]];find_focus(v[t],0);sz[rf]=sum-sz[root];get_xl(root);}return;
}
void get_xl()
{root=0; sum=n; son[0]=n;find_focus(1,0);sz[rf]=sum-sz[root];get_xl(root);return;
}
void dfs(int c,int fa)
{dep[c]=dep[fa]+1;if(dep[c]>U) return;fx[dep[c]]=Max(fx[dep[c]],dis[c]);for(int t=fir[c];t;t=nes[t]){if(v[t]==fa || vis[v[t]]) continue;dis[v[t]]=dis[c]+q[t];dfs(v[t],c);}
}
bool solve(int c)
{vis[c]=true;int now=0;bool judge=false;for(int t=fir[c];t;t=nes[t]){if(vis[v[t]]) continue;dis[v[t]]=q[t];dfs(v[t],0);int l=1,r=1; dl[1]=0;for(int i=1;fx[i]!=-INF;i++){while(now>0 && now-1+i>=L){now--;while(f[now]>=f[dl[r]] && r>=l) r--;dl[++r]=now;}while(dl[l]+i>U) l++;if(fx[i]+f[dl[l]]>=0) {judge=true;break;}}int i;for(i=1;fx[i]!=-INF;i++)f[i]=Max(f[i],fx[i]),fx[i]=-INF;now=Max(now,i);if(judge) break;}while(now--) f[now]=-INF;return judge;
}
bool check()
{bool judge=false;int i;for(i=2;i<=tot;i++) q[i]-=mid;for(i=1;i<=top;i++)if(solve(xl[i])) { judge=true; break; }while(i--) vis[i]=false;for(i=2;i<=tot;i++) q[i]+=mid;return judge;
}
int main()
{read(n); read(L); read(U);for(int i=1,x,y,z;i<n;i++){read(x);read(y);read(z);edge(x,y,z);maxn=Max(maxn,z);}get_xl();for(int i=0;i<=n+1;i++) f[i]=fx[i]=-INF,vis[i]=false;f[0]=0;l=0,r=maxn;while(r-l>=EPS){mid=(l+r)/2.0;if(check()) l=mid;else r=mid;}printf("%.3lf\n",l);return 0;}