Solution

A. DongDong破密码

定位签到题，仔细观察给出的样例，会发现第一行的数以下位和向左位是相同的，得出规律，维护之前位的异或值即可，整个序列扫一遍复杂度。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40760295

B. DongDong认亲戚

加并查集裸题，并查集就不谈了，我们可以把每一个读入的名字用map转换为数字，维护一下字符串和数字互相映射的关系，然后就用并查集维护一下是否属于同一个集合即可，理论复杂度是

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40760615

C. DongDong跳一跳

看过去就像个，用表示，上一步停在高度时最多已经吃到了个鱼干，所以从到的桶里找出最大值，然后更新一下现在这个高度的桶就好了,复杂度（有权值线段树优化的话可以变成）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40760617

D. DongDong坐飞机

分层图最短路，用表示到了这个点，已经用了次半价的情况下最小花费，然后可以转移到和，然后大力最短路跑一下就了，理论复杂度

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40760635

E. DongDong数颜色

做法1：dfs序+莫队，先把树上的点标上dfs序，因为子树的dfs序是连续的，所以子树可以表示为,然后就是序列上莫队了
做法2：DSU ON TREE，对于每个节点的子树开一颗线段树或者set，然后不断向上合并即可
做法3：考虑每个节点的贡献，点u对上一个颜色与点u相同的点的LCA贡献-1，u对自身贡献1，每个节点的ans就是子树贡献和，然后上个树状数组或者线段树维护一下就好。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40760637

F. DongDong的生成树

动态维护最小生成树,肯定是上LCT啊，动态加边的时候，如果当前两点不连通就直接连上，如果联通的话，连上这条边会形成一个环，我们可以任意删去环上的一边使其变回树，所以果断删掉里面边权最大的那条边啊。然后因为要删边，所以在LCT上需要维护最大值的pos

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40760678