理，很明显，这样生成的图，两点之间要么没有路径，要么唯一一条路径中权值的最小值最大。所以，我们只要先跑一次最大生成树，然后在求点对之间的树上路径最小值就可以了。
复杂度：O(mlogm+qlogn)
代码（C++）（MST+树上倍增）：
#include#include#includeusingnamespacestd;#defineMAXN10010#defineMAXM50010#defineMAXQ30010#defineMAXD20#defineclear(x)memset(x,0,sizeof(x))#defineAddEdge(s,t,d)Add(s,t,d),Add(t,s,d)#defineinf0x7fffffffstructsaver{ints,t,d;}e[MAXM];boolcmp(saverx,savery){returnx.d>y.d;}intfather[MAXN],n,m,q,Q[MAXQ][2];intFind(intx){inti,j=x;for(i=x;father[i];i=father[i]);while(father[j]){intk=father[j];father[j]=i;j=k;}returni;}intup[MAXN][MAXD],Min[MAXN][MAXD],h[MAXN];boolf[MAXN];structedge{edge*next;intt,d;edge(){next=NULL;}}*head[MAXN];voidAdd(ints,intt,intd){edge*p=new(edge);p->t=t,p->d=d,p->next=head[s];head[s]=p;}voidBuildTree(intv){f[v]=false;for(edge*p=head[v];p;p=p->next)if(f[p->t]){up[p->t][0]=v,Min[p->t][0]=p->d,h[p->t]=h[v]+1;BuildTree(p->t);}}intMove(int&v,intH){intrec=inf;for(inti=MAXD-1;i>=0;i--){if(h[up[v][i]]>=H){rec=min(rec,Min[v][i]);v=up[v][i];}}returnrec;}intQuery(intu,intv){if(Find(u)!=Find(v))return-1;intrec=inf;if(h[u]!=h[v])rec=h[u]>h[v]?Move(u,h[v]):Move(v,h[u]);//printf(\if(u==v)returnrec;for(inti=MAXD-1;i>=0;i--){if(up[u][i]!=up[v][i]){rec=min(rec,min(Min[u][i],Min[v][i]));u=up[u][i],v=up[v][i];}}rec=min(rec,min(Min[u][0],Min[v][0]));returnrec;}intmain(){clear(father),clear(head),clear(up);scanf(\,&n,&m);for(inti=0;i第一题：积木大赛（模拟）直接贪心，每次取最大一个连续区间，然后模拟即可。令h[0]=0,答案就是：∑h[i]-h[i-1](0h[i-1])复杂度:O(n)
代码1(Cpp)：
#include#defineMAXN100010inth[MAXN],ans=0,n;intmain(){h[0]=0;scanf(\,&n);for(inti=0;i++h[i-1])ans+=h[i]-h[i-1];}printf(\\\n\,ans);return0;}代码2（先对高度进行基数排序，然后逐行计算区间数，复杂度也是#include#includeO(n)）(Cpp):
usingnamespacestd;#defineMAXH10010#defineMAXN100010structnode{node*next;intt;node(){next=NULL;}}*head[MAXH];intmaxh=0;voidInsert(inth,intt){maxh=max(maxh,h);node*p=new(node);p->t=t,p->next=head[h];head[h]=p;}intn,h,delta=1,ans=0;boolf[MAXN];intmain(){memset(f,true,sizeof(f)),memset(head,0,sizeof(head));cin>>n;f[0]=f[n+1]=false;for(inti=0;i++>h,Insert(h,i);
loading