Description 

X国遭受了地震的重创, 导致全国的交通近乎瘫痪，重建家园的计划迫在眉睫。X国由N个城市组成, 重建小组提出，仅需建立N-1条道路即可使得任意两个城市互相可达。于是，重建小组很快提出了一个包含N-1条道路的方案，并满足城市之间两两可达，他们还计算评估了每条道路e建设之后可以带来的价值v(e)。

由于重建计划复杂而艰难，经费也有一定限制。因此，政府要求第一期重建工程修建的道路数目为k条，但需满足L ≤ k ≤ U, 即不应少于L条，但不超过U条。同时，为了最大化利用率，要求建设的这些道路恰好组成一条简单路径，即所建设的k条路径可以构成一个排列e1 = (p1, q1), e2 = (p2, q2), „, ek = (pk, qk), 对于 1 ≤ i < k, 有(qi = pi+1)。

重建小组打算修改他们的原有方案以满足要求，即在原有的N-1条道路中寻找一条路径S作为新的方案，使得新方案中的道路平均价值

\[AvgValue = \frac{\sum _{e \in S} v(e)}{|S|}\]

最大。这里v(e)表示道路e的价值，|S|表示新方案中道路的条数。请你帮助重建小组寻找一个最优方案。 注: 在本题中L和U的设置将保证有解。

Solution

它好毒瘤。。。我想哭！！！

打了大半天？我已经记不清楚时间了。

一开始疯狂Wa20，也不知道到底哪错了，大概是单调队列吧

• 二分答案

  所有边都减去那个值，原题转换为求是否有一条满足长度限制的链的边权和大等于0。

• 点分治

1. 对于每一个子树，我们只需要前面子树的点在不同深度(也就是长度)的最大值就好了。

2. 首先子树按照最大深度排序，用bfs取出子树的所有点，这样子点的深度连续。

3. 可以和该子树连接的区间也是连续的，用单调队列维护

   复杂度假装是\(O(nlog^2n)\)吧

下面奉上被改的面目全非的代码

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define MN 100005#define inf 1000000000LLint N,L,U,en,hr[MN];struct edge{int to;double v;int nex;}e[MN<<1];inline void ins(int f,int t,int v){    e[++en]=(edge){t,v,hr[f]};hr[f]=en;    e[++en]=(edge){f,v,hr[t]};hr[t]=en;}bool vis[MN];int mx[MN],siz[MN],sm,rt;int qur[MN],tot;inline void getroot(int x,int f){    siz[x]=1;mx[x]=0;register int i;    for(i=hr[x];i;i=e[i].nex)if((e[i].to^f)&&!vis[e[i].to])    {        getroot(e[i].to,x);        siz[x]+=siz[e[i].to];        mx[x]=max(mx[x],siz[e[i].to]);    }    mx[x]=max(mx[x],sm-siz[x]);    if(mx[x]
     
      x) x=y;}int qr,ql,n,qx[MN+5];void init(int x){qr=0;ql=1;n=x;}void ins(int x){    if(qr>=ql&&qx[qr]<=x)return;    if(qr
      
       n)return;    for(;mxdep[x]>=mxdep[qx[qr]]&&qr>=ql;--qr);    qx[++qr]=x;}double query(int x){    while(qx[ql]>x&&qr>=ql)++ql;    if(qr
       
        L-1;k--) ins(k);    for(i=1;i<=r;++i)    {        register int u=q[i];        if(dep[u]>U) break;        if(dis[u]>=0.&&dep[u]>=L&&dep[u]<=U){flag=1;return;}        if(dep[u]
        
         =0) {flag=1;return;}                for(j=hr[u];j;j=e[j].nex)            if((!vis[e[j].to])&&(e[j].to^fa[u])) q[++r]=e[j].to;    }    for(i=1;i<=r;++i) rw(mxdep[dep[q[i]]],dis[q[i]]);}std::vector
         
           ch[MN];void solve(int root){ register int i,j,k;vis[root]=true; maxdeep=0; for(i=hr[root];i;i=e[i].nex)if(!vis[e[i].to]) { tp=0;q[r=1]=e[i].to;fa[e[i].to]=root;dep[e[i].to]=1; dis[e[i].to]=(double)e[i].v*1.-mid;bfs(e[i].to); ch[tp].push_back(e[i].to);maxdeep=max(maxdeep,tp); } for(i=1;i<=maxdeep;++i)for(j=ch[i].size()-1;~j;--j) { q[r=1]=ch[i][j],BFS(ch[i][j],i); if(flag){for(k=1;k<=maxdeep;++k) ch[k].clear(),mxdep[k]=-inf;return;} } for(i=1;i<=maxdeep;++i) ch[i].clear(),mxdep[i]=-inf;}int main(){ N=read();L=read();U=read(); register int i,x,y; register double rans=1000000.,lans=0.; for(i=1;i
         
        
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！