[2018EC] Philosophical … Balance SAM+树形DP

题目大意

给定长度为 n n n的字符串 s s s，要求给定 s s s的每个后缀 s [ i : ] s[i:] s[i:]分配权值 k i k_i ki​（实数），满足 0 ≤ k i ≤ 1 0 \leq k_i \leq 1 0≤ki​≤1，且 ∑ i k i = 1 \sum_i k_i = 1 ∑i​ki​=1。在此基础上，最大化以下式子的值：
min ⁡ i = 1 n ( ∑ j = 1 n k j l c p ( s [ i : ] , s [ j : ] ) ) \min_{i=1}^n \left( \sum_{j=1}^n k_j {\rm {lcp}} (s[i:],s[j:]) \right) i=1minn​(j=1∑n​kj​lcp(s[i:],s[j:]))
要求答案输出最大的上式子的值。

题目分析

由于需要反复求后缀的的 l c p lcp lcp，不难联想到 S A M SAM SAM中节点的含义： S A M SAM SAM 的每一个节点表示的「 E n d p o s Endpos Endpos 集合相等的子串」的集合，在 P a r e n t T r e e ParentTree ParentTree 中，子节点的 e n d p o s endpos endpos 一定是父亲的真子集。而 E n d p o s Endpos Endpos 集合相等的子串均为某个前缀的长度连续的后缀。那么我们只需要把原问题做一下变换：

求原串后缀 l c p   → lcp\ \rightarrow lcp → 求反串前缀 l c p lcp lcp

因此，我们先对反串建立 S A M SAM SAM。然后，我们对代求式子进行转化：

设后缀 s [ i , n ] s[i, n] s[i,n](即为反串的前缀)在 S A M SAM SAM的 P a r e n t T r e e ParentTree ParentTree上的节点为 p i p_i pi​，那么此时代表的的反串 E n d p o s Endpos Endpos等价类相当于原串 S t a r t p o s Startpos Startpos等价类，那么对 p i p_i pi​和 p j p_j pj​求 L C A LCA LCA得到的 p L C A ( p i , p j ) p_{LCA(p_i, p_j)} pLCA(pi​,pj​)​的深度就是原串中的 l c p lcp lcp值。所以有：
max ⁡ min ⁡ i = 1 n ( ∑ j = 1 n k j × d e p p L C A ( p i , p j ) ) \max{\min_{i=1}^n \left( \sum_{j=1}^n k_j \times dep_{p_{LCA(p_i, p_j)}} \right)} maxi=1minn​(j=1∑n​kj​×deppLCA(pi​,pj​)​​)
由于问题转换到了树上，因此考虑树形 D P DP DP解决问题。令 d p [ i ] dp[i] dp[i]表示仅考虑以 i i i为根的子树的式子答案，显然初始 d p [ i ] = 1 dp[i] = 1 dp[i]=1，当子树答案向根节点合并时仍然是乘比例分配，因此最终分配方案总和仍为 1 1 1。

现在考虑子树答案如何计算：当把 x ( 1 ≤ x ≤ k ) x(1 \leq x \leq k) x(1≤x≤k)权值分给子节点 v v v时，对答案的贡献为：
x × d p [ v ] + ( 1 − x ) × d e p u x \times dp[v] + (1 - x) \times dep_u x×dp[v]+(1−x)×depu​
合并带 x x x的同类项：
x × ( d p [ v ] − d e p u ) + d e p u x \times (dp[v] - dep_u) + dep_u x×(dp[v]−depu​)+depu​
然后考虑最大化最小值问题，然后这里很懵逼，看了几篇题解都说根据纳什均衡，子树的贡献取值应尽可能地相等。另外一种解释是看作几个一次函数相加的结果，求一根扫描线的位置使得 ∑ x = 1 \sum x= 1 ∑x=1，应该让最小值变大，最大值变小，最终策略是都取中间值，即都相等。那么可以推出按照反比分配的方案，于是直接在 D P DP DP的过程中分配即可。

Code

#include 
#define int long long
#define endl '\n'
using namespace std;

const int N = 4e5 + 100, DICT_SIZE = 26;

struct SAM{
    int ch[N