(题目链接)

题意

　　给出一棵树，每条边有边权，问选出一条长度为$[L,U]$的路径，使得路径上的边权平均数最大是多少。

Solution

　　哈哈，爸爸终于过啦。

　　首先二分答案，然后路径统计显然点分治，统计答案的时候单调队列维护一下滑动窗口里面的最值。因为要点分治若干次，我们不妨将重心预处理出来，减少常数。

　　一定要小心，在点分治处理子树的时候，一定要按照深度从小到大的顺序处理，不然直接被新加的那组扫把型的数据卡掉T_T。

细节

　　清空cnt。

代码

// bzoj1758#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define LD long double#define eps 1e-4#define inf (1ll<<60)#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=100010;int n,m,U,L,cnt,head[maxn];struct edge {int to,next,w;}e[maxn<<1];struct data { int num,D; friend bool operator < (data a,data b) {return a.D>b.D;}};namespace NodeDivide { int Dargen,rt,D,maxD,sum,size[maxn],vis[maxn],Sum[maxn],f[maxn],q[maxn],h[maxn]; edge t[maxn]; double ans,deep[maxn],dis[maxn],Dis[maxn]; void link(int u,int v) {t[++cnt]=(edge){v,h[u]};h[u]=cnt;} void dfs(int x,int fa) { size[x]=f[x]=1; for (int i=head[x];i;i=e[i].next) if (e[i].to!=fa && !vis[e[i].to]) { dfs(e[i].to,x); f[x]=max(f[x],size[e[i].to]); size[x]+=size[e[i].to]; } f[x]=max(f[x],sum-size[x]); if (f[x]
            
              T; for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) { D=0;deep[e[i].to]=e[i].w; caldeep(e[i].to,x,1); T.push((data){e[i].to,D}); } while (!T.empty()) { data tmp=T.top();T.pop(); caldis(tmp.num,x,1); int l=1,r=0,pl=maxD,pr=maxD; for (int i=1;i<=tmp.D;i++) { for (;pl>-1 && pl>=L-i;pl--) { while (l<=r && Dis[q[r]]-q[r]*res
             
              -1 && pr>U-i;pr--) while (l<=r && q[l]>=pr) l++; if (pl
              
               =L) solve(t[i].to,res); vis[x]=0; } void caldargen(int x,int fa) { vis[x]=1; if (fa) link(fa,x);else Dargen=x; for (int i=head[x];i;i=e[i].next) if (!vis[e[i].to]) { sum=size[e[i].to],rt=0; dfs(e[i].to,x); Sum[rt]=sum; caldargen(rt,x); } vis[x]=0; } void Init() { cnt=0; sum=n;f[rt=0]=1<<30; dfs(1,0);Sum[rt]=sum; caldargen(rt,0); } double main(double res) { ans=-inf; solve(Dargen,res); return ans; }}using namespace NodeDivide;void link(int u,int v,int w) { e[++cnt]=(edge){v,head[u],w};head[u]=cnt; e[++cnt]=(edge){u,head[v],w};head[v]=cnt;}int main() { scanf("%d%d%d",&n,&L,&U); for (int u,v,w,i=1;i
               
                =0) l=mid+eps,ans=mid; else r=mid-eps; } printf("%.3lf",ans); return 0;}