《Fairy》解题报告.pdfVIP

《Fairy》解题报告 中山纪念中学 梁健楠 【题源】 本题来自CODEFORCES 19E—— 《Fairy》 【前言】 本题是一道树形DP题，程序实现并不难，但考验选手的思维能力。 【题目大意】 给定N个点，M条边的无向图，从中删除一条边，要求对图上的点进行黑白染 色，任意相邻的两点都不同色。 问：满足要求的边数，以及具体哪些边满足要求？ N，M 10000。 样例输入: 样例输出: Case 1: Case 1: 4 4 4 1 2 1 2 3 4 1 3 Case 2: 2 4 1 3 4 5 Case 2: 4 5 1 2 2 3 3 4 4 1 1 3 【问题分析】 首先在图中找出颗生成树，然后对点进行染色，保证树边两端点的颜色不同。 对于非树边，将两端点颜色不同的非树边称为合法非树边，将两端点颜色相 同的非树边称为不合法非树边。 讨论删除非树边： 当删除一条非树边后，并不影响生成树的结构，因此，不能修改端点的颜色。 换句话说，删除一条非树边，不合法非树边依然是不合法的。 假如不存在不合法非树边，那么可以删除任意一条非树边； 假如只存在一条不合法非树边，那么只能删除该条非树边； 假如存在多条不合法非树边，那么任意非树边都不能删除。 讨论删除树边： 当删除一条树边后，生成树会断开成两块连通块。对其中一块连通块的所有 点取反色，依然能保证树边两端点的颜色不相同，而连接两块连通块的不合法非 树边会变成合法，合法的会变成不合法。 由此可知，要使删除一条树边后满足要求，必须使得所有不合法非树边连接 着两块连通块，并且任意一条合法非树边不连接着两块连通块(特殊判断不存在 不合法非树边的情况)。 统计删除某条树边后，有多少合法非树边和不合法非树边连接两块连通块。 考虑非树边和生成树会产生一个环，删除该环上的树边，则该非树边连接两个连 通块。对于每一条非树边，只要维护它所在的环上的树边的信息。 具体实现可用动态规划： f[i][0]记录删除树边 i 时有多少不合法非树边连接两块连通块，f[i][1] 则记录合法非树边。 g[i][0]标记边两端LCA (最近公共祖先)为i 的不合法非树边数，g[i][1]则 记录合法非树边。 转移时，求某点的f 值，只需将其子结点的f 值求和，减去其g 值。 为了更好地求LCA，生成树可选取dfs 树。 至此完美地解决问题，算法的时间复杂度为O(M)。 【程序实现(pascal)】 {$M 1000000000} var N,M,Num,ans,k,i,x,y:longint; boo:boolean; w:array[-11000..11000,1..2]of longint; g,d:array[0..11000]of longint; f,jf:array[0..11000,0..1]of longint; u:array[-11000..11000]of boolean; jans:array[0..11000]of boolean; procedure con(x,y,z:longint); begin w[z][1]:=y; w[z][2]:=g[x]; g[x]:=z; w[-z][1]:=x; w[-z][2]:=g[y]; g[y]:=-z; end; procedure dfs1(x:longint); var j,nx:lon