看起来啥都不会

先来思考那个子问题，给出\(2\times k\)个树上关键点，让这些关键点两两匹配，使得\(k\)对匹配的边权和最小

不妨考虑树上差分，众所周知，让路径\((x,y)\)上边权加\(1\)只需要另\(x,y\)点权加\(1\)，\(\rm LCA(x,y)\)点权减\(2\)，再求一下子树和即可

先将\(2\times k\)个关键点的点权都加\(1\)，现在我们需要选择\(k\)个\(\rm LCA\)，让这些\(\rm LCA\)的点权都减\(2\)，由于我们最后需要最小化所有被经过的边权和，于是我们需要让这些\(\rm LCA\)尽可能地深

设\(d_x\)表示点\(x\)子树内部有多少个关键点，显然\(d_x=\sum_{v\in son(x)}d_v\)，我们让这些关键点两两匹配，就形成了\(\left \lfloor \frac{d_x}{2} \right \rfloor\)组匹配，于是我们让\(x\)点权减去\(2\times \left \lfloor \frac{d_x}{2} \right \rfloor\)，同时\(d_x\)也会变成\(d_x-2\times \left \lfloor \frac{d_x}{2} \right \rfloor\)即\(d_x\rm mod\ 2\)

于是\(d_v\)也只可能是\(0\)或\(1\)，即一个儿子最多也只能上传给父亲一个未匹配的关键点，所以并不会出现在\(x\)处匹配的\(\rm LCA\)不是\(x\)的情况

得出所有点的点权之后，做一遍子树和即得到了每一条边被经过的次数，我们就能计算最小匹配了

暴力枚举所有长度为偶数的区间，于是我们得到了一个\(O(m^2n)\)的优秀做法

考虑一下这个算法带来的启示

首先一条边被经过的次数一定不会超过\(1\)，可以考虑对于每一条边计算出其再多少个区间里被经过

同时还由于每一个点的\(d\)只可能是\(0\)或\(1\)，当\(d_x=0\)时，就说明\(x\)内的关键点在\(x\)子树内部就已经匹配完了，不需要和\(x\)外面的关键点匹配了；当\(d_x=1\)时，说明\(x\)子树内部有一个未匹配的关键点，由于这个关键点一定要和\(x\)子树外的点匹配，所以\(x\)到其父亲的那一条边一定会被经过

显然\(d_x\)即\(x\)子树内部关键点个数的奇偶性，于是当一个点子树内部有奇数个关键点时，这个点到其父亲的边一定会被经过

现在我们只需要对于每个点，求出有多少个长度为偶数的区间，使得其子树内部有奇数个关键点

我们可以大力\(\rm dsu\ on\ tree\)，对于每一个点求出一个桶\(tax\)，\(tax_i\)表示给出序列上的第\(i\)个点是否在这个点的子树内部出现过

现在我们只需要求这个桶有多少个长度为偶数的区间异或和为\(1\)即可

考虑对这个桶做一遍前缀异或和，\([l,r]\)区间长度为偶数且异或和为\(1\)需要满足，\(r-l+1\equiv 0(\rm mod\ 2),pre_r-pre_{l-1}\equiv 1(\rm mod \ 2)\)，即\(l-1\)和\(r\)的奇偶性相同，\(pre_r\)和\(pre_{l-1}\)的奇偶性不同

于是我们开两棵线段树，分别维护奇位置和偶位置的前缀异或和，单点修改变成了后缀取反，线段树随便维护一下就可以了，复杂度\(O(n\log^2n)\)

代码

#include
    
     #define re register#define LL long longconst int mod=998244353;const int maxn=1e5+5;inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}std::vector
     
       v[maxn];struct E{int v,nxt,w;}e[maxn<<1];int deep[maxn],sum[maxn],fa[maxn],son[maxn],id[maxn],head[maxn];int n,m,num,s[2],ans,S;inline void add(int x,int y,int z) {    e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=z;}struct Segment_Tree {    int l[maxn<<1],r[maxn<<1],tag[maxn<<1],g[maxn<<1],len[maxn<<1],cl[maxn<<1];    void build(int x,int y,int i) {        l[i]=x,r[i]=y;len[i]=r[i]-l[i]+1;        if(x==y) return;        int mid=x+y>>1;        build(x,mid,i<<1),build(mid+1,y,i<<1|1);    }    inline void pushdown(int i) {        if(cl[i]) {            cl[i]=0;cl[i<<1]=cl[i<<1|1]=1;            g[i<<1|1]=g[i<<1]=tag[i<<1]=tag[i<<1|1]=0;        }        if(!tag[i]) return;tag[i]=0;        tag[i<<1]^=1;tag[i<<1|1]^=1;        g[i<<1]=len[i<<1]-g[i<<1];        g[i<<1|1]=len[i<<1|1]-g[i<<1|1];    }    void change(int pos,int i) {        if(l[i]>=pos) {            g[i]=len[i]-g[i];            tag[i]^=1;return;        }        pushdown(i);        int mid=l[i]+r[i]>>1;        change(pos,i<<1|1);        if(pos<=mid) change(pos,i<<1);        g[i]=g[i<<1]+g[i<<1|1];    }    inline void clear() {cl[1]=1;g[1]=tag[1]=0;}}T[2];void dfs1(int x) {    sum[x]=1+v[x].size();    for(re int i=head[x];i;i=e[i].nxt) {        if(deep[e[i].v]) continue;        deep[e[i].v]=deep[x]+1;dfs1(e[i].v);        sum[x]+=sum[e[i].v];        fa[e[i].v]=(e[i].w>=mod?e[i].w-mod:e[i].w);        if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;    }}void calc(int pos) {    T[pos&1].change(id[pos],1);    if(pos
      
       deep[x]) dfs(e[i].v,0);    if(son[x]) dfs(son[x],1),S=son[x];    solve(x);int now=0;    now=1ll*T[0].g[1]*(s[0]-T[0].g[1])%mod;    now=(now+1ll*T[1].g[1]*(s[1]-T[1].g[1])%mod)%mod;    ans=(ans+1ll*now*fa[x]%mod)%mod;    if(!k) T[0].clear(),T[1].clear();}int main() {    n=read();m=read();    for(re int x,y,z,i=1;i