BZOJ 4025. 二分图

BZOJ 4025. 二分图

DarkBZOJ 传送门
https://www.cnblogs.com/ZeonfaiHo/p/7502056.html

题意

给定一个 n 个点, m 条边的无向图, 每条边在一定时间范围内存在. 要你判断每个时间点这张图是否为二分图。(n ≤ 1e5,m≤2e5)

题解

我们可以用 Link-Cut Tree 离线的维护图的连通性,方法是我们把图当成树来处理,维护出路径上最脆弱的边(也就是最早消失的边)即可,当新插入的边连接的两个点已经处在一个连通分量时,如果新的边更加健康,我们就去替换掉那条边,关于 Link-Cut Ttre 维护路径最值的操作,参考 HDU 4010

(这好像其实也就是 Link-Cut Tree 最正经的用途之,优化网络流!)

回到这个题,我们只需要再维护一下路径的 size,判断一下是否有奇数个点(或者偶数条边)即可,由于现在考察的对象既有边又有点,还有换根操作,着实容易写错,干脆的把原图中的边也放进 Link-Cut Tree 里去维护。

代码

BOI 2020

BOI 2020

Day 1

传送门
HackMD
竞プロ日常

Problem A. Colors

题意

交互式问题,给定 n,每次你可以将头发染成 1-n 中间的一个数字,如果相邻两次的数字差的绝对值 >= C,那么男朋友会注意,返回 1,否则返回 0。每个颜色只能用一次,用尽可能少的询问找到 C。

题解

很优雅的倍增构造。

Problem B. Mixture

题意

动态维护若干瓶调味料,每瓶调味料中装有一定质量的 盐,胡椒与大蒜 的混合物,给定美食家最喜欢的调味料的组成,每次询问,可以增加一瓶新的调味料或者删除一瓶之前添加过的调味料,返回至少需要几瓶可以混合出美食家最喜欢的口味。

题解

不会。

Problem C. Joker

题意

给定一张有 n 个点 m 条边的无向图,每次询问给出一个区间 [L, R],问是否存在奇环,使得环中不包含区间中的点。

题解

是否存在奇环,等价于二分图判定。静态可以 dfs,动态的话可以 dsu,最后外面套一层莫队算法即可。

当然也可以直接用 lct!

对于删除 [l, r] 区间的边,我们可以用类似破环为链的方法,转化为每次询问保留 (r, l+m) 区间的边,显然边越少越容易合法,满足单调性。我们按照时间顺序依次插入所有边,用 double-point 维护出处理到时间 r 时,最大的 l 使得当前的状态合法即可。这样就可以贴 BZOJ 4025 的代码了。

Day 2

传送门
竞プロ日常

Problem A. Graph

题意

给定一个边被红、蓝染色的无向图,求一组节点的权值方案,满足对所有的红边,关联的节点的权值和为 1,对所有的蓝边,权值和为 2,满足条件的基础上,最小化所有节点的权值和。

题解

让人想起了之前 Atcoder 上的一道染色的题。不过这个题是实数。做法是随便找个点和初始标记一路 dfs 下去把每个节点标记成 ax+b 的形式,其中 a 属于集合 {-1, 0, 1},x 是一个待定系数,最后算出 x 的值即可,需要一些 insight。

Problem B. Village

题意

给定一个树,求两组错位排列的方案 P,分别使得 \sum dist(i, P[i]) 的权值和最大和最小。

题解

首先最小的话显然尽可能交换相邻的结点编号就好了,我们就每次找叶子,如果没有交换过,就和父节点交换,这样最后有可能还剩一个,没关系随便找一个相邻结点再交换一次就好。

对于最大的情况,我们考察每条边 (u,v),那么这条边贡献的上界是 min(sz[u], sz[v]),我们发现可以构造方案让所有边的上界都达到,方法是只要考察重心,让每个点都标记在另一颗子树中即可。

这样看的话,似乎是需要找一下重心的。。。但是 最快的提交代码 直接就上了。。只要证明这样构造之后,可以找到一个节点作为根,使得每个节点都不落入同一子树中就行了。。而这是显然的,因为以重心分割的话,子树的 size 不会超过 n/2。

Problem C. Viruses

题意

基因序列是一个由 n 种数字形成的字符串,其中 0、1 为终止字符,其他为病毒字符,给定一张基因突变的表格,每个表格表示一个病毒字符可能会突变成的基因串,一个基因序列每一秒中,会有一个病毒字符突变,一些病毒字符可能有多种突变方向。给定一些模式串作为抗体,问每个病毒字符所能形成的最短的,不被任意一个抗体所识别的终止序列的长度(或者输出不存在)。

题解

没有病毒串的时候显然可以用类似最短路的方法 dp 出最短长度。。有病毒串的时候开个自动机就好。。由于我们需要支持合并字符串的操作,所以 dp 状态需要加维,记录在自动机中的状态区间,具体说来就是 dp[i][st][ed] 表示基因 i 展开之后,从状态 st 到状态 ed 的最短路径长度。

冲了一发 果断 TLE 了。虽然本质上是最短路模型,但是本题的边是广义的,可能会与多个节点关联,Dijkstra 着实不太好写,所以用了 Bellman_Ford,考虑到瓶颈主要在松弛(Relax)操作上(每次都要跑一遍神似 Floyd 的 DP),感觉改成 SPFA 可过。

换了 SPFA 之后还是有一个点过不去,看来本题数据还是很良心的。。

看了一下其他人的搞法,最快的 WZYYN 同学非常厉害,直接 Bellman_Ford 加了一个奇怪的剪枝就过了,然后 duality 看起来是常规的 SPFA,在 Relax 的时候跳过了无穷的情况,原理就跟一些矩阵乘法的题目,需要优化掉内层循环的取模差不多。

然后 BenQjiangly 的给都是 Dijkstra 正解。最猛的是 liouzhou_101,直接卡时,居然还卡过去了 Orz。。。(所以我也卡时吧。。> <。。。

BZOJ 2125: 最短路

BZOJ | Luogu
https://cmxrynp.github.io/2018/10/29/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF/
https://blog.csdn.net/LPA20020220/article/details/88887231

题意

给你一个有 n 个点和 m 条边的仙人掌图,和 q 组询问,
每次询问两个点之间的最短路。

题解

圆方树

const int N = int(2e4) + 9, LV = 15;

VII adj[N], adjj[N];
int dfn[N], low[N], tt, sta[N], top;
int fa[LV][N], dep[N], D[N], DD[N], L[N];
int n, nn;

inline int move_up(int x, int t){
for (int lv=0;t;++lv,t&gt;&gt;=1)
if (t&amp;1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x;
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
return fa[0][x];
}
void getLCA(int x, int y, int &amp;a, int &amp;b, int &amp;z) {
if (dep[x]&gt;dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;}
DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
a = x; b = y; z = fa[0][x];
}

void add_edge(int u, int v, LL w) {
adjj[u].PB(MP(v, w));
}

#define v it-&gt;fi
#define w it-&gt;se
void tarjan(int u = 1, int p = -1) {
low[u] = dfn[u] = ++tt;
sta[++top] = u;
ECH(it, adj[u]) if (v != p) {
if (!dfn[v]) {
D[v] = D[u] + w; tarjan(v, u);
checkMin(low[u], low[v]);
if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge
} else if (dfn[v] &lt; dfn[u]) { // find circle
            checkMin(low[u], dfn[v]);
            add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w;
            for (int i=top;sta[i]!=v;--i) {
                int d = D[sta[i]]-D[v];
                add_edge(nn, sta[i], min(d, L[nn]-d));
            }
        }
    }
    --top;
}
#define p fa[0][u]
void dfs(int u = 1) {
    ECH(it, adjj[u]) {
        dep[v] = dep[u] + 1; DD[v] = DD[u] + w;
        fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
        dfs(v);
    }
}
#undef p
#undef w
#undef v

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    int Q, m; RD(n, m, Q);

    DO(m) {
        int x, y, w; RD(x, y, w);
        adj[x].PB(MP(y, w));
        adj[y].PB(MP(x, w));
    }

    nn = n; tarjan(); dfs();

    DO(Q) {
        int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z);

        //cout &lt;&lt; x &lt;&lt; " " &lt;&lt; y &lt;&lt; " " &lt;&lt;  z&lt;&lt; endl;

        if (z &lt;= n) { // round one ...
            OT(DD[x]+DD[y]-DD[z]*2);
        } else { // square one ...
            int d = abs(D[a]-D[b]);
            OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d));
        }
    }
}

动态仙人掌

https://www.luogu.com.cn/record/31868182

论自杀

论自杀

最近确实有点快要支撑不下去了的意思呢 … 明明自己前几天自己还在劝说兔子要好好活下去来着?最直接的理由自然还是 公司的事情,我已经被逼到悬崖边上了。。。没有公章一大堆公司的合同(员工入职,办公室更换)现在都处理不了,因为回不了国收不到法人的电话,公司账户还有随时被冻结的危险,这个理由很难理解吗?本来创业就已经是困难重重的事情,就算大家都齐心协力,也不一定会取得结果。。。但是我实在接受不了因为这样的原因而结束。。没人指望你输出,至少不要扯我们的后腿吧?。。。为什么要给大家添麻烦呢?,,,每次想找 T 好好讨论解决事情,但是人家根本就不想理你,说多了就变成了「疯狂骚扰」和「疯狂污蔑」。。。就应该被打断腿。。。这还是隔着几层屏幕讨论事情的结果。。更不用想象见面讨论会是怎样的场面了。。。我到现在都依然没有理解,,,就算想要开启新的生活,,,不是应该把公章的事情一次性解决掉才更好吗?。。。或者交给任何其他人也都可以,,,为什么一定要把我逼到如此绝境?。。。。。我真的做了什么十恶不赦的事情吗?。明明我每次遇到问题都是一再退让的啊。。。。

前几天一个人在洛杉矶机场的时候,在看到自己的航班再一次的被取消之后,一个人推着满载三个行李箱大小的手推车,寻思着接下来去哪里的时候,孤独和无助感瞬间萦绕全身,明明有那么多不得不回去的理由的。。事实上我的航班前一天和后一天都有出发的。。。只能怪自己运气不好。。。继续在机场逗留。。还会让自己过多的暴露在病毒之下。。。我还没有医保。。。一旦中招,孤独的客死他乡都是完全有可能的。。。

。后来我还找兔子认真的讨论了「自杀」这件事情。。。我当时只是觉得,如果真的要「自杀」的话,应该怎么做都会成功吧。。最简单的方法可能是,找个高楼大厦,忘记一切,跳下去就好。。。而且在都市圈的话,卧轨应该也是很多人的一个选择。。不过兔子说,那样会麻烦到其他人。。打扫起来很不方便,烧炭的话,如果失败会变成植物人。。。(所以果然还是「静脉注射氯化钡」最好?。。。)。。

不过我想真的要是绝望到需要寻死的地步。。。那个时候,我还能为其他人思考这么多吗。。。?。。再说 每年身边自杀的 mtf 那么多,多死一两个。。。应该没有什么人会在意吧?。。。

分类

先看看 Wikipedia 上怎么说。。。

在动机上主要可分为两种:
– 主动型自杀,为达成个人因素以外的目的而进行的自杀。例如,自杀攻击是为达到某种目的而自杀。(E.g. 三岛由纪夫)
– 被动型自杀,仅个人因素导致的自杀。比如逃离性自杀,例如社会压力而产生心理疾病、药物、醉酒、物质滥用等,是外因导致其自杀。(E.g. 阿兰图灵)

一般来说,主动者受时空背景影响至甚。相较于主动者,被动者在自杀意念发生时,呈现较明显的低自尊与负向思维倾向。缺乏自信的人较可能发生被动型自杀,忧郁症患者的自杀几乎全属被动型。

文明发展愈高的地区,对社会的不满愈少,故被动型的比率愈高。

在行为模式上的类型有:
– 安乐死:个体以借助他人帮助的形式来完成自己的自杀。
– 谋杀自杀:一个人用谋杀的方式,让另一个人或几个人在他本人之前或同时死去。
– 相约自杀:两个或两个以上的个体之间立下协定,通常是因个人原因,同时或先后自杀。
– 集体自杀:集体自杀指一群人为了同一目的而自杀或互相杀害,而这通常与真实或意识到的迫害有关。(代表作,乱步奇谭)

主动型自杀

  • 自杀式袭击:牺牲自己以完成攻击目的。如神风特攻队、恐怖攻击中的自杀炸弹客。
  • 政治目的性自杀:为传达某种理念而自杀,例如死谏、殉情或以死明志,例如在某重要地标自焚。此类自杀亦常见要求他人协助完成者。如2019年自杀的香港反对修订逃犯条例示威者、郑南榕。

被动型自杀

  • 胁迫性自杀:为了控制他人(罪恶感、恐惧)而自杀。因认为自己遭到某人恶意待遇(因动机来自感受到他人恶意,故列为被动型),而以死的方式作为报复手段。某些地方文化认为人死后产生的鬼可代为复仇,亦属这一类。
  • 责任性自杀:为了显示责任心而自杀,如早期日本在战败时的切腹自杀(因具备文化因素,亦含主动性成分)。在现代,此类自杀常见于强迫性格倾向者。(E.g. 如最近负责日本武汉撤侨的首相官邸官员)
  • 逃离性自杀:为了躲避某种事物(如恶疾、痛苦、恐慌、空虚等感受),或是被某事逼迫(如被逼债、畏罪、政权垮台),因而自杀。(大部分情况)

所以我这种大概属于逃离性自杀了。。我确实不知道该怎么走出现在的困境了。

方式

「还有什么比创作出来的故事更真实的呢?」
—— 【剩余榨值023】在巨大的 shock 后,我们所思考的、所做的一切都将与此有关 34:00

介于 推上的投票给的选项太少了。。这里重新罗列一下。。大概我能想到的。。包括真实的和虚构的作品:

坠楼

作品:梦日记(附窗子)、乱步奇谭(小林),返校(方芮欣),神雕侠侣(杨过*)、天使不在 12 月(雪绪)、大时代、圣人大盗

おやすみ世界 #ゆめにっき16周年

梦日记

。。自杀自然是十分诱人的… 所有描绘自杀的作品里。。最令人印象深刻的自然还是《梦日记》。在梦中辛苦游历收集了所有十二扇门的世界。最后的最后。。居然是选择结束了自己的生命。。。留给玩家无限多的想象空间。。。

乱步奇谭

乱步奇谭的结尾也是关于自杀的描写,而且还是「集体自杀」,所不同的是,在最后的关头,小林被班长救了下来。。。从而达成了一个 Happy Ending。。看完最后一集才意识到其实这个结局其实早在 ED 的 PV 里就已经暗示给读者了。。。多米诺骨牌暗示着「集体自杀」,而最后这个画面暗示了小林被救下。。。

返校

关于,方芮欣是跳楼还是上吊而死的似乎坊间还有 一些争议

在返校的开场就可以看见一个仿佛女主自己身影的幻想从楼上跳下去,在加上仲庭的手札,有寫「那人一躍而去,就此離開人世,未曾留下隻字片語。」,推断方芮欣应该是跳楼而死。虽然游戏后段 Bad End 的地方又有多处关于上吊的描写,大概这只是一种赎罪的意象。

自刎

哪吒《哪吒鬧海》、虞姬、项羽《霸王别姬》、黄得功《桃花扇》

哪吒闹海

哪个 mtf 小时候没有一个反复出现的剔骨还父的梦呢?(当然,家长党就当我没说。。)。。。出处就是这里。。(使得在很长一段时间里,我甚至认为中国人的自杀等价于自刎。。。日本人的自杀等价于剖腹。。。)。。。

私以为,哪吒人生的高光时刻就在于拔剑自刎的那一瞬间(如同孙悟空的高光时刻约等于大闹天宫时把玉皇大帝打到桌肚下面一样。。)。。

爹爹,我一人做事一人当,你的骨肉我还给你,我不连累你!

遗憾的是。。这么一个重要的意象。。。在最近的所有关于哪吒的作品里。。都被有意识或者无意识的削弱或忘却了。。。

霸王别姬

再然后自然就是《霸王别姬》了。。。就是大家语文课都学过的那篇课文。。。

「吾闻汉购我头千金,邑万户,吾为若德。」
—— 《史记 项羽本纪》

当然觉得项羽你是不是傻啊。。回去切一下假腿。。再来过就是了。。
而且临死之前还送人头给人家发育。。。

生当作人杰,死亦为鬼雄。
至今思项羽,不肯过江东
—— 李清照《夏日绝句》

后来随着阅历的增长。。多少稍微能理解李清照这首诗歌的含义了。。。
这种境界果然不是刘邦什么的可以比的。。。。

「汉兵已略地,四面楚歌声。大王意气尽,贱妾何聊生!」

再然后就是回到《霸王别姬》里程蝶衣和袁四爷舞剑这一段,我的理解是如果袁四爷这一秒没有制止的话,程蝶衣绝对会因为入戏太深而刺下去。(因为下一个画面所流的眼泪沾湿了妆容。。。)。。

最近又读了一遍《伶人往事》,里面程砚秋后来对戏剧的态度,书中写到:

「我们演一个剧,第一要自己懂得这个剧的意义,第二要明白观众对于这个戏的感情……还有人以为戏剧是用来开心取乐的,以为是玩意儿,其实不然」,「一个戏总有它的意义,算起总账来,就是一切戏剧都有提高人类生活目标的意义」

很多作品里都有这种戏里戏外互相映射的设定,如「庄生晓梦迷蝴蝶」之感。例如《霸王别姬》里程蝶衣《思凡》预示性别认同障碍,小赖子唱《夜奔》预示着他会逃出戏班。红楼梦第十八回「賈元春歸省慶元宵」所点的四出折子戏,也全部都是暗示了相关人物的命运,「所點之戲劇伏四事,乃通部書之大過節、大關鍵。」

自缢

作品:亚伦·斯沃茨、打工战士《Steins;Gate》菊仙《霸王别姬》、Sayori《Doki Doki Literature Club! ?》

互联网之子

前段时间在推上写 亚伦·斯沃茨、爱德华·斯诺登、朱利安·阿桑奇和中本聪 的时候,回去重新看了一遍《互联网之子》,显然,至亲至爱之人的背叛是压垮亚伦的最后一根稻草。当然现在谁都没有办法还原出当时事件的完整情况了。。。

霸王别姬

因至亲至爱之人的背叛,在文革中自缢而死的人,应该不在少数吧。。。

Steins;Gate

TBD

Doki Doki Literature Club! ?

TBD

沉江

作品:屈原、桃花扇(史可法)、红楼梦(林黛玉)

屈原可以算是沉江的鼻祖了吧。。小时候看过《上下五千年》好像留有了一个残存的印象。。已经不真切了。。。。最近看到的应该还是《桃花扇》。。。有一段关于史可法沉江的描写(明明你好不容易才杀出重围不是吗?。。)。。。齣目名就叫做《沈江》。。。

「俺史可法亡國罪臣,那容的冠裳而去。」
「你看茫茫世界,留著俺史可法何處安放。累死英雄,到此日看江山換主,無可留戀。」

。。。

这种大概也是符合我的美学的自杀方式。。。最好还是海葬。。。

我希望可以死在大海里。。。
溺水而死。。。。
毕竟是岛嘛。。。
回归地球🌍母亲的怀抱。。。
—— 小島 みなこ, [Jul 10, 2020 at 7:25:44 PM]

服毒

作品:模仿游戏(图灵)、苏菲的世界(苏格拉底)、t(逆转裁判)

饮弹

作品:云图(罗伯特)、最后生还者(亨利)、不要和陌生人说话(冯远征)

云图


云图你的音乐家,在把他的重要之物(物理学家的马甲)当出去的时候,就已经有下定决心要轻生的念头了吧,大家在自杀之前,都会先把自己的重要之物,转交出去,如果还有的话。。。可是他寻死之前还是做了最后一件事情。。。就是把云图六重奏给完成。。。这样大概也是死的没有遗憾了。。。

最后生还者

黑人兄弟的死 是《美末》里非常棒的一段演出,完美的渲染出了末世的感觉,这种弄出一对镜像视角先死一遍从而酝酿压迫感的手法,在粉粉粉粉粉的《救了个命》的开场也有使用。特别是亨利的死,前一秒还拿着枪对着乔尔,后一秒突然就举枪自尽,非常的突然。。。

不知为何,这一季的编剧为什么看起来智商掉线了,我打算等云完之后再来好好谈谈《美末2》。。。。

割腕

作品:unlight(雪莉)

卧轨

作品:安娜卡列尼娜

烧炭

作品:???

触电

生死观

子曰:「未知生,焉知死」。

记得以前玩《轩辕剑云与山得彼端》调查墓碑旁边的人,他会:

「人死之后,葬在地下,占得多少土地?」

所以墓碑的话,还是留在线上好了,参见 People Die, but Long Live GitHub

而那一處墓碑上面寫著。。。

「墳中安葬着丟番圖。上帝給予的童年佔六分之一,又過十二分之一,兩頰長胡,再過七分之一,點燃起結婚的蠟燭。五年之後天賜貴子,可憐遲到的寧馨兒,享年僅及其父之半,便進入冰冷的墓。悲傷只有用數論的研究去彌補,又過四年,他也走完了人生的旅途。」

我好喜欢这种生死觀…。舉重若輕,等到死亡真正降临的時候。。面對死神略帶著一點玩笑和調侃。。還留下了一道題目。。給晚輩们以啟發。。
(类似的还有最近的 “Flight recorder inventor: Do Not Open”

而最糟糕的大概是讓遺體住在水晶棺材裡。。。
靈魂永遠得不到安寧。。。

未竟之事

TBD

SPOJ CAKE3. Delicious Cake

Vjudge | SPOJ | TG

先复习一下 插头 dp 大字典。本题显然使用染色模型。轮廓线上只有 m 个位置,而且不需要 roll() 操作(不过生成的新插头,要求前面的区分开来,所以我们还是用 m+1 来标记)。这样搞得话,2×2 我们会算出答案等于 14,仔细观察,是因为我们多算了下面两种不合法的情况。

我们发现这类情况都是因为在前面的转移中产生了刻痕,而使得后续的插头合并不合法,需要进一步编码。
我们可以给每个连通块强行上一个颜色,不相同的颜色不可合并。但是因为原问题没有颜色,这样计数起来会比较麻烦(需要最小染色,并且必须保证相同颜色的连通块必被合并)。
我们也可以暴力记录 C(5,2) 个连通块之间是否产生过刻痕,这样合并的时候直接判断即可。

刻痕的维护,首先每次状态转移,当前插头都需要和相邻两个插头(左插头和上插头)都标记刻痕。
其次,因为我们使用了最小表示,连通块的记号会被 relable,因而编码的时候也需要重新映射。
最后插头合并的时候,刻痕信息也需要合并。

最后上一下高精度模板就好了。留个 OEIS 地址方便大家 debug。

UOJ 87. mx 的仙人掌

参考资料

官方题解
https://blog.bill.moe/uoj87-mxcactus/

题意

给定一个仙人掌,每次从中选取几个关键节点,求它们之间两两之间距离的最大值。

题解

对于树的情况,如果你只会虚树或者树分治,对于仙人掌你肯定也只能这么做了。
—— 官方题解

所以这个题乃会几种做法,取决于树的版本的那个问题,你会几种做法。官方题解 的六、七、八、九,提供了四种思路。这里先实现第一个算法 —— 虚仙人掌。

虚树

先当成树做,拿个 30 分再说。。。这里我用 f[] 数组记录向下的最长距离,然后在更新 f[u] 之前,先用 f[v] 和 f[u] 一起更新一下全局的直径,这样就不需要记录次大值了!

http://uoj.ac/submission/387435

虚仙人掌 (a.k.a. 圆方树)

首先对这类题目来说,通常的做法,是 dfs 的时候,找到环,然后再环上手工 dp 一次(但其实我总是敲错,需要依靠底力),把经过环的结果统计到答案,并更新到环上的根节点。
事实上对于 BZOJ 1023. [SHOI2008]cactus仙人掌图IOI 2008 D2T1 Islands 我们就是这样做的(分别是 直径 和 最长链,转移方程几乎一样)。

但我们发现并不是总能靠底力凹出来,比如 BZOJ 2125: 最短路,树上两点的最短路需要求 lca,仙人掌上怎么求 lca,似乎需要大量 if-else 判断 = =!!!
这个题的情况类似,因为在构建虚树的过程中,我们也需要求 lca。

这个时候我们就需要使用一种 常用的技巧 圆方树。参见 圆方树——处理仙人掌的利器

简单说来,圆方树就是把环边都去掉,新建一个 方点 来代替这个环,用环上的根节点连一条边到她,在从她到每个环上的其他节点连一条边,形成菊花形状以拆环为树(怎么样?是不是很像 block-cut tree)。

具体实作的话,先建三个结构体,分表表示 —— 原图,圆方树,虚树。分别记作 G,C,T。求圆方树的过程,可以类比 tarjan 求双联通分量,我这边是在最深的节点拉回反向边的时候,把环抠出来的(因而需要取个反)。
这里连向方点的权值为 0,而从方点连出的边的权值为左右两条路径的长度取 min。

紧接着在 C 上再 dfs 一次,预处理出 dp 和 lca 所需要的信息,为构造虚树做准备。最后求虚树的地方,和 之前写的代码 唯一的不同,是如果是从方点连出去的边,需要把这个环上连出去的那个孩子也加到树中,因为我们需要这些节点来正确处理环上的 DP。

void add_edge(int x, int y) {
if (x &gt; G.n &amp;&amp; x != C.fa[0][y]) { // 如果是从方点连出去,并且 y 不是连出去的那个孩子。
int z = C.move_up(y, C.dep[y]-C.dep[x]-1);
adj[x].PB(z);
x = z;
}
adj[x].PB(y);
}

这个地方也是之前裸凹的时候最麻烦的地方,因为现在有了圆方树,所以几行就处理了掉了w。

接下来是下一个容易错的地方,以样例来说,在建立虚树的时候我们会把 2 和 9 所在的这个环也加到虚树里,而这个环本身的信息有可能会节外生枝,包含一些本不应该被考虑到节点(这里是 7),所以我们更新答案的时候干脆只用圆点的信息更新即可(上面 add_edge 里补上的节点并不会影响)。

参见 下图

最后说一个让我 wa 成傻逼的地方,就是最后的资源回收。。。因为这种虚树的题通常我们是不能无脑 memset 的,但是我们刚才构建虚树的时候,中间又加入了一些新的节点,所以直接 for 循环那个数组的话会错。。
所以,最好在遍历树结束的同时把这些不用的信息都清理掉。。。

http://uoj.ac/submission/387655