洛谷-P11345 [KTSC 2023 R2] 基地简化 题解

校内模拟赛题倒在了正解前最后一步 qwq。解题思路首先发现题目要求的东西很不好做。于是转化一下考虑计算每条边对答案贡献了几次。这样问题就转化成了求有多少个区间的点分布在一条边两端的两个子树中。发现这个东西还是不好求。于是正难则反考虑计算区间的点全部在同一个子树里的区间数量。显然这个数量可以通过set维护子树内外点的编号所形成的连续段实现。但实现起来细节较多需要注意各种边界问题。如果暴力地对每棵子树都把节点挨个insert一下去算这个东西复杂度就是O(n2log⁡n)O(n^2 \log n)O(n2logn)的会直接 T 飞。我们使用树上启发式合并优化这个过程。时间复杂度O(nlog⁡2n)O(n \log^2 n)O(nlog2n)。Code#includebits/stdc.h#definerep(i,a,b)for(inti(a);ib;i)#definerept(i,a,b)for(inti(a);ib;i)#definefifirst#definesesecond#defineintlonglongusingnamespacestd;constexprintN3e55,P1e97;vectorpairint,intg[N];intn,tim;intans;intl[N],r[N],siz[N],up[N],ch[N],rk[N];signedmaintenance_costs_sum(vectorsignedU,vectorsignedV,vectorsignedW);inlineintcalc(intx){returnx*(x1)/2%P;}structSet{setpairint,ints;// 存的是不在集合内点的编号形成的连续段inttot;voidclear(){s.clear();s.emplace(1,n);totcalc(n);}voidinsert(intx){autoitprev(s.lower_bound({x,n1}));intlit-fi,rit-se;if(lxxr){(tot-calc(r-l1))%P;(totcalc(1))%P;(totcalc(x-l))%P;(totcalc(r-x))%P;s.erase(it);s.emplace(l,x-1);s.emplace(x1,r);return;}intlmits.begin()?0:prev(it)-se;intrmnext(it)s.end()?n1:next(it)-fi;if(lr){(tot-calc(l-lm-1))%P;(tot-calc(rm-r-1))%P;(tot-calc(1))%P;(totcalc(rm-lm-1))%P;s.erase(it);return;}if(lx){(tot-calc(r-l1))%P;(tot-calc(l-lm-1))%P;(totcalc(r-l))%P;(totcalc(l-lm))%P;s.erase(it);s.emplace(l1,r);return;}if(rx){(tot-calc(r-l1))%P;(tot-calc(rm-r-1))%P;(totcalc(r-l))%P;(totcalc(rm-r))%P;s.erase(it);s.emplace(l,r-1);}}}st;voidadd(intl,intr){rept(i,l,r){st.insert(rk[i]);}}voiddfs(intu,intpre){l[u]tim,rk[l[u]]u,siz[u]1;for(auto[v,w]:g[u]){if(vpre)continue;up[v]w;dfs(v,u);siz[u]siz[v];if(siz[ch[u]]siz[v])ch[u]v;}r[u]tim;}voiddsu(intu,intpre){st.clear();for(auto[v,w]:g[u]){if(vpre||vch[u])continue;dsu(v,u);st.clear();}if(ch[u])dsu(ch[u],u);for(auto[v,w]:g[u]){if(vpre||vch[u])continue;add(l[v],r[v]);}add(l[u],l[u]);(ansup[u]*(calc(n)-st.tot))%P;}signedmaintenance_costs_sum(vectorsignedU,vectorsignedV,vectorsignedW){nU.size()1;rep(i,0,n-1){intuU[i]1,vV[i]1,wW[i];g[u].emplace_back(v,w);g[v].emplace_back(u,w);}dfs(1,0);dsu(1,0);return(ansP)%P;}