ABC略
D
找到所有山峰(注意这里 (1,N) 也算)往两边路径最大值,如果有相同那么后手只需和先手选择同样高度的山峰对应的山谷即可获胜。
否则找到唯一的山峰,考虑往两边的路径大小不同,那么后手可以在高的部分调整奇偶性,先手还是必败。否则奇数时必胜。
E
考虑 (m=3k) 的情况,把 (j=2,5,8...) 全部画X,然后再稍微调整之间的连线即可。
这同样可以做 (m=3k+2) 的情况。
(m=3k+1) 时最后会多出一行不好考虑。重新在 (1,4,7...) 位置画X,然后按上述做法做即可。
F
数据范围这么小考虑枚举 (i,j)。
求出 (dis[i][j]) 代表最短路+1。
若 (dis[i][k]+dis[k][j]=dis[i][j]+1) 则 k 必在 i,j 最短路上。
如果这样的 k 比 dis[i][j] 多说明有两条以上最短路。
i只会从一条进入,而 j 一定从每条都出去,所以答案是 0 。
然后考虑其他点的贡献,枚举父亲,算出可能有几种情况,乘再一起即为答案。
判断父亲的条件 : (dis[i][k]=dis[i][fa]+1and dis[j][k]=dis[j][fa]+1)。
因为只是算这个点的父亲,所以答案互不影响,可以直接相乘。