Good Bye 2023
https://codeforces.com/contest/1916
E. Happy Life in University(1s,512mb)
n(3e5)个点,根1的树, 每个点有颜色,求$\max(diff(u,lca(u,v)) * diff(v,lca(u,v)))$
其中$diff(u,v) =$,简单路径u到v上不同颜色的个数
我的思路
有想过dp,但是显然dp[u] =
最长向下路径,是不行的因为 向上转移时需要知道是否有对应颜色
如果u,v是最大的方案
- u,v没有祖先关系,那么u,v可以走到其下的任意位置,答案不会更差
- u,v是祖先关系,那么一个向根走,一个向叶子走, 答案不会更差
因此 ans = max(f(叶子,叶子),f(根,叶子))
对于最近同色也是 可以简单的dfs+按照颜色的栈来做, 这样可以O(n)计算出每个点最近同色祖先
想过把树按照dfs序铺平成数组, 这样需要支持一种叫 整线段贡献
1 | 对于颜色c |
这样就变成 对于u,
找[in[u]....childa...] x [in[u]....childb...]
问题是这样支持线段后,如果直接用前缀和就有问题了