A最长路
先考虑所有字符都相等的情况，相当于只用求以每个点为起点的最长路的长度。
对反向图进行拓扑排序，所有在环中的点最长路都是无限长，对于其他点dp，f_x表示以x为起点的最长路的边数，则
。特别的，若x没有出边，则f_x=0。
。特别的，若x没有出边，则f_x=0。 下面考虑所有字符互不相等的情况。
多记一个g_x，表示以x为起点的最长路的哈希值
则
其中y是所有满足f_x可以从f_y转移过来的y中 w_{x,y} 最小的那个。特别的，若x没有出边，则g_x=0。
下面考虑一般的情况。 我们需要快速比较两个方案的字典序大小。
注意到，处理到x时，前面的点的转移边都确定了，所以可以使用倍增+哈希来快速求出两个方案第一个不同的字符，然后比较大小。 时间 O(n+mlogn)，期望得分100
方法二：
将所有点按最长路分层，依次处理每一层，
将上一层连向这一层的所有边按边上的字符为第一关键字，
起点的排名为第二关键字排序，
然后更新这一层的答案，得到这一层的排名。
时间 O(n+mlogn) ，瓶颈在排序。
期望得分100
将所有点按最长路分层，依次处理每一层，
将上一层连向这一层的所有边按边上的字符为第一关键字，
起点的排名为第二关键字排序，
然后更新这一层的答案，得到这一层的排名。
时间 O(n+mlogn) ，瓶颈在排序。
期望得分100
B选择题
第 x 个人的答案 =
其中 p(x,mx,cx) 表示第 x 个人选了第 cx 个选项，
且
的概率。
且
的概率。 下面考虑如何计算 p(x,mx,cx) 。
定义 f(x,mx,cnt) 表示除了 x 以外的人中恰好有 cnt 个人选了第 mx 个选项的概率。
则
下面考虑如何计算 f(x,mx,cnt) 。
对于一个给定的 mx ，现在的问题相当于，第 i 个人有 p_i 的概率选(第mx个选项)，有 1-p_i 的概率不选，对 x=1...n，求除了第 x 个人以外恰好有 cnt 个人选的概率。
一个简单的想法就是对每个 x 都做一遍 dp 。 枚举除了 x 以外的每个人， dp_cnt 表示当前集合(即所有已经枚举过的人)恰好有 cnt 个人选的概率，假设新加进来的人有 p 的概率选，考虑如何更新 dp 数组。
因为有 p 的概率多了一个人选，1-p 的概率不变。 令原来的数组为 dp0 ，加入这个人后的数组为 dp' ，则
这样时间复杂度是 O(n^3) 的，期望得分55。
方法二：
dp 求出 pre_{i,j} 表示前 i 个人恰有 j 个人选的概率， suf_{i,j} 表示后 i 个人恰有 j 个人选的概率。
考虑求除第 i 个人外有 >= j 个人选的概率，只需对 pre 求个后缀和，然后枚举即可。
时间 O(n^2) 。
由于常数较大，期望得分55-100
注意到我们不仅支持向集合中加入一个人后O(n)维护dp数组，还支持删除一个人后O(n)维护dp数组。
也就是说，给定 dp' 和 p ，可以推回 dp0 。(注意p=1的情况需要特判)
所以先 O(n^2) 求出全集的 dp 数组，然后对每个 x ，O(n) 求出不含 x 的 dp 数组即可。
时间复杂度 O(n^2)，期望得分100。
dp 求出 pre_{i,j} 表示前 i 个人恰有 j 个人选的概率， suf_{i,j} 表示后 i 个人恰有 j 个人选的概率。
考虑求除第 i 个人外有 >= j 个人选的概率，只需对 pre 求个后缀和，然后枚举即可。
时间 O(n^2) 。
由于常数较大，期望得分55-100
C树
注意到，第二种操作x y col_1 col_2实际上可以拆成几个操作：
1 将x到y路径上每个点指向儿子的边的颜色改为col_2
2 将x到y路径上每个点指向父亲的边的颜色改为col_1
3 将x和y的lca指向父亲的边的颜色改为col_2
1 将x到y路径上每个点指向儿子的边的颜色改为col_2
2 将x到y路径上每个点指向父亲的边的颜色改为col_1
3 将x和y的lca指向父亲的边的颜色改为col_2
所以这题实际上就是4种操作：
链询问，链修改指向儿子的边，链修改，换根+子树修改
链询问，链修改指向儿子的边，链修改，换根+子树修改
如果没有"链修改指向儿子的边"这个操作的话，这题可以树链剖分+线段树。
前两种情况都对应着dfs序上的一段连续区间，
第三种情况则对应着dfs序上的两段连续区间，
所以都可以直接在线段树上区间修改。
有个小问题就是第三种情况时如何求y，可以使用倍增或者树链剖分。
时间复杂度O(n+mlog^2)，期望得分100
std
A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=37074141
线段树上一个结点代表树上一个连续的dfs序区间的点指向父亲的边。
如果rt在x在原树的子树外面，那么以rt为根时x的子树就等同于x在原树中的子树；
如果rt=x，那么以rt为根时x的子树就是整棵树；
如果rt在x的某个儿子y的子树中，那么以rt为根时x的子树就是整个树除去y在原树中的子树。
每个结点记录区间内各个颜色的出现次数，区间修改的标记。
链询问就对log条重链和log条轻边分别询问；
链修改就对log条重链和log条轻边分别修改； 换根+子树修改需要分类讨论：
将以1为根的树称为原树。如果rt=x，那么以rt为根时x的子树就是整棵树；
如果rt在x的某个儿子y的子树中，那么以rt为根时x的子树就是整个树除去y在原树中的子树。
前两种情况都对应着dfs序上的一段连续区间，
第三种情况则对应着dfs序上的两段连续区间，
所以都可以直接在线段树上区间修改。
有个小问题就是第三种情况时如何求y，可以使用倍增或者树链剖分。
现在考虑"链修改指向儿子的边"这个操作。
考虑对每个点维护一个信息to_son，表示这个点指向儿子的轻边被修改成了什么颜色。 "链修改指向儿子的边"时，
所有被修改的重边被分成了log条重链，直接在前面那个线段树上修改；
而所有被修改的轻边则不直接改，而是修改父亲结点的to_son，这里需要再用一个线段树维护。
所有被修改的重边被分成了log条重链，直接在前面那个线段树上修改；
而所有被修改的轻边则不直接改，而是修改父亲结点的to_son，这里需要再用一个线段树维护。
在询问的时候，
重边还是一样，直接在前面那个线段树上面询问；
轻边则需要比较前面那个线段树上的结果(儿子指向父亲的边)和后面那个线段树的结果(父亲的to_son)，哪个更迟选哪个，
只需要线段树上多记录一个修改的时间就可以了。
重边还是一样，直接在前面那个线段树上面询问；
轻边则需要比较前面那个线段树上的结果(儿子指向父亲的边)和后面那个线段树的结果(父亲的to_son)，哪个更迟选哪个，
只需要线段树上多记录一个修改的时间就可以了。
时间复杂度O(n+mlog^2)，期望得分100
全部评论
(0) 回帖