通过子任务1、3十分显然，子任务4实际上就是线段树，和我下午写的一模一样，堪称“我抄我自己”，不会的可以先做一下这个题。

然后考虑正解，参考了，首先可以对前i列做MST，就是把前i-1列和第i列合并起来，而这时候只需要把第1和第i列的点作为关键点建立虚树，虚树边权为原树路径最大值，然后每次O(n)对虚树合并即可。后缀也同样做一遍即可。查询时，就是把整张图分成两半，同样只需要维护前后缀的左右两列建立虚树即可，复杂度O(n(m+q)logn)

#include
      
       using namespace std;typedef long long ll;const int N=10086;struct edge{
    int u,v,w;};bool operator<(edge a,edge b){
    return a.w
       
        G;struct MST{    int tot;ll sum;    vector
        
         G;    MST(){}    MST(int*c)    {        tot=n,sum=0;        for(int i=1;i
         
          >5,SA^=SA<<1;    unsigned int t=SA;    SA=SB,SB=SC,SC^=t^SA;    return SC%lim+1;}int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);}void adde(edge x){    v[++cnt]=x.v,nxt[cnt]=hd[x.u],w[cnt]=x.w,hd[x.u]=cnt;    v[++cnt]=x.u,nxt[cnt]=hd[x.v],w[cnt]=x.w,hd[x.v]=cnt;    ans+=x.w;}bool dfs1(int u,int f){    int ret=0;    for(int i=hd[u];i;i=nxt[i])if(v[i]!=f)ret+=dfs1(v[i],u);    vis[u]|=(ret>=2),ret+=vis[u];    return ret;}void dfs2(int u,int f,int lst,int val){    if(vis[u])    {        if(lst)G.push_back((edge){vis[u],lst,val});        lst=vis[u],ans-=val,val=0;    }    for(int i=hd[u];i;i=nxt[i])if(v[i]!=f)dfs2(v[i],u,lst,max(val,w[i]));}MST merge(MST a,MST b,int*c){    G.clear(),tot=a.tot+b.tot;    for(int i=0;i
          
           tot-n),hd[i]=0;    ans=cnt=0;    for(int i=0;i
           
            1;i--)suf[i]=merge(MST(d2[i]),suf[i+1],d1[i]); scanf("%d",&Q); while(Q--) { int l,r;scanf("%d%d",&l,&r); printf("%lld\n",query(merge(suf[r+1],pre[l-1],d1[m]))); }}