P4606 [SDOI2018] 战略游戏

狗屎 虚树 + 圆方树。

顺便第一次打 欧拉序求 LCA。

注意特判根节点的情况即可，甚至不需要 dp。

P4334 [COI2007] Policija

sblhy 直接给我交题解了，那我就不打了。

说一个最重要的点：如何判断树上 \(z\) 在 \(x,y\) 的简单路径上？

dfn 序：满足两个条件。

1. \(x,y\) 至少有一个在 \(z\) 的子树中。

2. \(z\) 在 \(lca(x,y)\) 的子树中。

树剖：在跳 LCA 的过程中判断被删点是否在起终点之间，我们用链首和深度判断即可。参考：

	inline bool LCA(int x,int y,int z){
		while(top[x]!=top[y]){
			if(dep[top[x]]<dep[top[y]])swap(x,y);
			if(top[x]==top[z] and dep[z]<=dep[x]) return 1;
			x=fa[top[x]];
		}
		if(dep[x]<dep[y])swap(x,y);
		if(top[x]==top[z] and dep[z]>=dep[y] and dep[z]<=dep[x]) return 1;
		return 0;
	}

倍增：简单的，不提及。