D Robert Hood and Mrs Hood

赛时对l,r分别进行了排序,来测算是否有事件进入，实际上这是没有必要的。

可以直接用一个桶来记录。buc[l]--,buc[r+1]--即可。

不难，时间复杂度为\(O(n)\)

E - Rendez-vous de Marian et Robin

赛时魔改dijkstra没有改出来(实际上应该也很难改出来) 赛后了解到分层图，直接开悟 做法是对每个节点，建图建一个有马节点，一个无马节点，有horse的节点就让无马节点向有马节点连边。对于给出的边，有马图和无马图同步建图。最后跑一遍Dijkstra就行。

F - Sheriff's Defense

由于给出的是树形结构，可以当作一颗有根树。 和图最大的不同点是这样的树上问题可以做到无后效性(考虑树上dfs，不会有背向边或者横叉边)，换言之就是可以dp/dfs (虽然我一开始想试试贪心，但是最后也没有试出来，而且时间复杂度上是不如dp的，实现上也比dp难，所以说dp好啊) 由于一个节点有两种状态，每个节点的贡献仅由这个节点和相邻节点决定。 于是我们考虑有根树上的状态转移： 两个相邻节点都取的话，总贡献减去\(2c\) 取\(S_u\)为\(u\)节点的子节点集合，\(dp[u]\)为子树的贡献

\(dp[u][0] = \sum_{v\in S_u} \max(dp[v][0],dp[v][1])\) \(dp[u][1] = \sum_{v\in S_u} \max(dp[v][0],dp[v][1]-2c)\)

实现用dfs实现即可。

核心代码： 

1
2
3
4
5
6
7
8
9
10
11
12
//dp1用a[i]初始化
dfs()
{
    for (int i = 0; i < g[p].size(); i++) {
        if (g[p][i] != fa) {
            dfs(g, a, dp0, dp1, g[p][i], p, c);
            dp0[p] += max(dp0[g[p][i]], dp1[g[p][i]]);
            dp1[p] += max(dp0[g[p][i]], dp1[g[p][i]] - c * 2);
        }
    }
    return;
}