首页 > 其他分享 >P8867 [NOIP2022] 建造军营

P8867 [NOIP2022] 建造军营

时间:2023-10-13 22:24:06浏览次数:37  
标签:连通 edg P8867 2f 军营 NOIP2022 prod

面对他。

题面:

求选择关键点和不会被割的边,使得任意割去一条边关键点不会有不连通的方案。

考虑缩边双,然后这样边双内随便选。
你考虑画出一颗树,考虑分类情况,容易发现就是三种:
1.没有选。
2.全部连通上 \(x\)。(即一个尚未孤立的连通块)。
3.有不联通到 \(x\) 的点。(即孤立的一个连通块)

第三种情况显然就是只存在一个连通块的方案。

记其为 \(f_{x, 1/2/3}\)

\[f_{x, 1} = 2^{edg + m} \prod^{m} f_{y, 1} \]

\[f_{x, 2} = 2^{edg + sz_x} \prod^{m} {2 * f_{y, 1} + f_{y, 2}} - 2^{m + edg}\prod f_{y, 1} \]

\[f_{x, 3} = 2^{edg}\sum^{m} (2f_{y, 3} + f_{y, 2}) \frac{\prod^{m}f{y,1}}{2f_{y, 1}} \]

分开转移即可。

哎,究竟有啥水平呢??哎。
究竟有啥水平呢??

标签:连通,edg,P8867,2f,军营,NOIP2022,prod
From: https://www.cnblogs.com/Custlo/p/17763388.html

相关文章

  • NOIP2022 比赛
    Day\(2^2+3^2+4^2\)。HNOI2016序列的加强版。我去年怎么这么菜啊,虽然现在也是就是了。\[\sum\limits_{[l,r]\in[L,R]}\left(\max\limits_{i\in[l,r]}a_i\right)\left(\max\limits_{i\in[l,r]}b_i\right)\]考虑离线,对右端点\(r\)扫描线,对每个左端点\(l\)维护\(S_l=\le......
  • P8867 [NOIP2022] 建造军营
    这道题想了很久,终于想出来了,非常抽象。经过一番无脑推导,我们发现u里面有没有军营,是否与根连通,u的子树有没有军营,……都对方案数有影响,然后我就一直修修改改,事实证明,当发现越来越多题目条件中被忽略的细节时,一定不要嫌麻烦,要从头开始设置状态。首先我们发现,子树中有没有军营对于......
  • 【22NOIP提高组】建造军营(barrack)
    include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constllM=1e9+7;llfast_pow(lla,llb){llres=1;while(b>0){if(b&1)res=(resa)%M;;a=(aa)%M;b>>=1;}returnres;}constintN=6e5+5;intn,m;structEdge{intu,......
  • P8868 [NOIP2022] 比赛
    https://www.luogu.com.cn/problem/P8868我学会了历史和!在一阵扫描线过后,你会发现,\([l,r]\)的所有子区间的答案,就一定是扫到\(i\)的时候,加上\([k,i]\)的答案,\(k\lei,i\in[l,r]\),然后又因为只有当\(i\gel\)的时候,才能对左端点在\([l,r]\)的答案贡献,因此,你会发现这个东......
  • 【题解】NOIP2022
    怎么看T3也不是那么难,可是为啥赛时就是被卡死了[难过]不补\(B\)题了,ad-hoc。A.种花题目描述:小C决定在他的花园里种出\(\texttt{CCF}\)字样的图案,因此他想知道\(\textttC\)和\(\textttF\)两个字母各自有多少种种花的方案;不幸的是,花园中有一些土坑,这些位置无法种......
  • CSP&NOIP2022游记
    今年是最后一年了,真的是来划水的了已经无欲无求了,只是最好能有个七级吧,要是没有也无所谓,反正我自始至终都是个OI废物已经完全回归whk咯谢幕之战,你会变好,还是更烂?冷知识:从去年CSP结束至今,Bosun在LG上只做了9题初赛前一天住了旅馆,周边玩了一下,感觉苏州古城区真的是一点意思也......
  • 【游记】NOIP2022 游记
    updateon:2023.6.7名字回归正常了,说明没有大寄。Day0具体细节忘记了,就迷迷糊糊地到了酒店(司机倒车技术不错)。晚上又跟lzh,fj,xwk,玩generals.io。2V2,我跟lzh一队,不知道玩了多少把,一直都是我们赢,他们心态直接崩了,不跟我们玩了。发现时间已经21:00,赶紧复习模板,发现还有......
  • [NOIP2022] 比赛
    \(\mathcalLink\)大半年前,我在没有难题的NOIP大败而归,以一个耻辱的分数。注意到询问具有分治性。考虑类似线段树一样拆分询问,然后考虑跨过\(\textit{mid}\)的子区间贡献。对于一个固定的\(r\),考虑\(l\)的贡献。记\(f\),\(g\)分别代表\(A\)和\(B\)对应区间的最值......
  • NOIP2022游寄
    挂大分+考试失误(还是食力不够/kk)\(Day\)-\(114514\)至\(Day\)-\(1\)whk+口胡题目+Water(大部分时候都是Water)。\(Day0\)一整天都在疯狂打板子。图论打了\(5,6\)个,数据结构\(5,6\)个,数论\(10\)多个。网课关了摄像头就是水。晚上被很多\(dalao\)祝福,希望rp++。躺......
  • 「回忆录」NOIP2022游寄
    都已经过去半年了才来更的屑距离CSP还有一周左右的时间,我们停课了,然后来了东校。Al:“为了庆祝我们在一起学习,下午我们考试!”???好像就呆了\(1\)天半,因为疫情,我们要提前出发去日照,然后中午家长们紧急把东西送来,Al跑回一区把ycc和zxs接来,三区的wxf和fjh下午也来了,然......