bzoj 2500 幸福的道路树上直径+set-白红宇

bzoj 2500 幸福的道路树上直径+set

阅读量：6764 次

发布时间：2019-06-26

本文共 1081 字，大约阅读时间需要 3 分钟。

首先明确：树上任意一点的最长路径一定是直径的某一端点。

所以先找出直径，求出最长路径，然后再求波动值<=m的最长区间

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define N 1000005using namespace std; int fa[N],cal[N],dis[2][N],d[N]; int e=1,head[N]; struct edge{ int u,v,w,next;}ed[N]; void add(int u,int v,int w){ ed[e].u=u; ed[e].v=v; ed[e].w=w; ed[e].next=head[u]; head[u]=e++;} int L,R,it,maxn; bool bo[N]; void dfs(int x,int len){ bo[x]=1; if(len>maxn) it=x,maxn=len; if(!bo[fa[x]]) dfs(fa[x],len+cal[x]); for(int i=head[x];i;i=ed[i].next){ if(!bo[ed[i].v]) dfs(ed[i].v,len+ed[i].w); }} int q[N],h,t; void bfs(int x,int wh){ bo[x]=1;int now,v,w; dis[wh][x]=0; q[1]=x; h=t=1; while(h<=t){ now=q[h++]; if(fa[now]&&!bo[fa[now]]&&dis[wh][fa[now]]

ss; int dd,xx,ll=1,ans=0; for(int i=1;i<=n;i++){ ss.insert(d[i]); dd=*(--ss.end()); xx=*(ss.begin()); while(dd-xx>m) ss.erase(ss.find(d[ll++])),dd=*(--ss.end()),xx=*(ss.begin()); ans=max(ans,i-ll+1); } printf("%d\n",ans); return 0;}

然而我打的依旧很蠢。。QAQ

转载于:https://www.cnblogs.com/Ren-Ivan/p/7746752.html

你可能感兴趣的文章

What is hd0 and sda/sdb in Linux?

查看>>

【转】C++内存分布

查看>>

why websocket over ajax