题意: 构造最小方差生成树

首先我们先从方差的定义出发可知  方差必定是一段连续的值 方差最小

最暴力的方法是 我们枚举平均数 然后转化最小生成树check 明显的复杂度太高 

我们考虑到每条边都有一个作用区间 因为当加入某一条边形成环时 为了维持稳定的方差 我们需要将这个环里面的最小边踢掉(至于为什么 可以手动模拟一下

这样的话 我们就把问题简化成插入或者加入某一条边 来维护Σwe^2和Σwe 很显然的 这是LCT加速即可

这个题 在场上并没有转化成区间 不然还可以搏一下 赛后补题遇到了三个问题:

1.在加边和删边维护LCT是取最小方差不应该在模的意义下

2.因为我们考虑的是枚举每一条边的最小方差 也就是说每条边都要构造一颗最小方差树 那也就是要离线将后面权值比较大但是又独一无二的边先加入进来 也就是当处理有环时应该同时加入边和最小边(不用分先后)

3.然后就是写戳了...还好抢救成功

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define ll long longconst int MAXN=5e5+10;using namespace std;const int mod=998244353;const int inf=1e9;int pre[MAXN],ch[MAXN][2],res[MAXN],pos[MAXN];ll key[MAXN];int cnt;int st[MAXN],tp;pair
         
          d[MAXN];bool rt[MAXN];int n,m;typedef struct node{    int u,v,vul;    friend bool operator<(node aa,node bb){        return aa.vul
          
           >1; } return ans;}typedef struct Node{ int vul;ll sum1,sum2; friend bool operator<(Node aa,Node bb){ if(aa.vul==bb.vul)return aa.sum1
           
            =0)cnt2++; else cnt2--,p[i].sum1++; ans1+=p[i].sum1;ans2+=p[i].sum2; // cout<
            
             <<" "<
             
              <
              
               make_pair(h,l)){ h1=h;h2=l; } } } printf("%lld\n",((h1+h2*ans3)%mod*ans3%mod)); } return 0;}