2023.4.27 下午 LZY 讲题
ICPC2022 Shenyang - G
题意
给定 \(n\) 个点的两颗树 \(T_1,T_2\)。\(m\) 次询问 \((a,b)\)，求 \(\max\limits_x\{d_1(a,x)+d_2(x,b)\}\)。
\(n\leq10^5,q\leq5\times10^5\)。提交地址 https://codeforces.com/gym/104160/problem/G。
分析
考虑若给定 \(a\)，询问 \(b\)，求 \(\max\limits_x\{d_1(a,x)+d_2(x,b)\}\)。考虑在 \(T_2\) 的每个节点 \(x\) 上挂上一个附属节点 \(x^\prime\)，边权 \(d_1(a,x)\)。则在 \(T_2^\prime\) 上，\(d(b,x^\prime)=d_1(a,x)+d_2(x,b)\)。先求一遍直径，显然直接分别从两个端点算一遍取 \(\max\) 即可。
考虑将询问离线下来，接下来就是解决 \(a\) 顺着一条边 \((u,v,w)\) 移动的贡献，显然对于 \(v\) 的子树附属边权 \(+w\)，非 \(v\) 子树附属边权 \(-w\)。考虑用线段树维护直径，线段树上的区间 \([l,r]\) 表示在 \(T_1\) 上 dfn 序区间 \([l,r]\) 对应到 \(T_2^\prime\) 的直径。在 \(T_1\) 上面 dfs 一遍，顺便处理询问，复杂度 \(\mathcal O(n\log^2n+q\log n)\)。如果用欧拉序加上 ST 表处理，可以做到 \(\mathcal O(n\log n+q)\)。
code
还没写呢……
ICPC2022 Nanjing - J
题意
给定一张 \(n\) 个点的无向图，每个点有个属性 \(a_i\)，两个点 \((i,j)\) 之间右边当且仅当，\(|i-j|=|a_i-a_j|\)。求这张图是否存在完美匹配。
\(n\leq10^5\)。提交地址 https://codeforces.com/gym/104128/problem/J。
分析
先说句废话，如果 \(n\) 为奇数，显然没有完美匹配。
看到绝对值，肯定是直接拆看一下有什么结论，上面的条件等价于 \(i+a_i=j+a_j\) 或 \(i-a_i=j-a_j\)。所有可以将问题强化（化简）成：每个点给定两个属性 \((a_i,b_i)\)，若 \(a_i=a_j\) 或 \(b_i=b_j\) 就连边。也就是说可以构造一个二分图，其中左部点 \(a_i\) 像右部点 \(b_i\) 连边 \((a_i,b_i,i)\)，有公共点的两条边就在原图上右边。
不难发现不同连通块之间相互独立，所以可以抽出一个连通块单独考虑。如果边数为奇数，显然不存在完美匹配。先建出一颗 dfs 生成树，从下往上考虑，对于当前节点 \(u\)，考虑所有还未被匹配的儿子边和以它为上端点的返祖边，若边数为奇数就加入父边。这些边两两随便匹配即可。
code
还没写呢……