咕了2天才写的题解还是比较经典的题目，分治处理网格图最短路离线下来，利用分治的思想，用一条线把网格图平均劈成两半，每次只考虑询问在两块的一对点，所有的线必须经过直线上的一个点，于是我把线上所有点都在规定范围内跑一次dijkstra，最后直接算答案，显然我想让最短路跑的次数最小，每次选

P3349[ZJOI2016]小星星树形dp+子集反演有一张图和一棵树，点数都为\(n\)，给树上的每个点一个映射\(a_i\)，每个\(a_i\)不同，\(a_i\in[1,n]\)。要求对于树上所有\((u,v)\)，都有\((a_u,a_v)\)在图上。求映射方案数。看到\(n\)的范围，可以想到树形状压dp。设\(F_{i,j,S}\)

P3350[ZJOI2016]旅行者分治+最短路网格图可以想到分治。每次将长边分为两半，处理越过中线的询问。那么就可以枚举中线上的每个点更新答案，经过\(x\)的路径更新\((u,v)\)就是\(dis_{u,x}+dis_{x,v}\)。每次预处理中线上每个点的单源最短路即可。设\(S=nm\)，复杂度\(O(S\sq

标签:子集反演,动态规划[ZJOI2016]小星星题目描述小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有\(n\)颗小星星，用\(m\)条彩色的细线串了起来，每条细线连着两颗小星星。有一天她发现，她的饰品被破坏了，很多细线都被拆掉了。这个饰品只剩下了\(n-1\)条细线，但通

[ZJOI2016]小星星题目描述小Y是一个心灵手巧的女孩子，她喜欢手工制作一些小饰品。她有\(n\)颗小星星，用\(m\)条彩色的细线串了起来，每条细线连着两颗小星星。有一天

绝世容斥好题，刚好NOIp前要复习容斥，就拉过来当100紫了。祝自己明天的NOIprp++这题好久前看过题解，感觉好可惜，浪费了好题。以后自己不会的题也不能看题解了。题意：