Description：

给一个字符串 $s$ ，确定一组 $p_i$ ，求： $$ \min_{p_i}(\max_{j=1}^n(\sum_{k=1}^np_klcp(s_k,s_j))) $$ $1\leqslant \sum n\leqslant 5\times 10^5$

Solution：

其实这是一个纳什均衡，但是本题并不用，如果我们把后缀树建出来那么答案就是： $$ \min_{p_i}(\max_{j=1}^n(\sum_{k=1}^np_kdep[lca(k,j)])) $$ 先考虑一个简单情况，如果是一棵二叉树应该怎么做，我们可以考虑用树形 $DP$ 来求解，设 $f[i]$ 表示为子树中的所有代表后缀的点分配一个 $\sum p=1$ 的权重之后只考虑这个子树内的点上面那个式子的值，考虑怎么把一个二叉树的两部份合并，我们肯定是为左边分配一个权值 $w_1$ ，右边分配一个权值 $w_2$ ，然后内部的权值被重新划定成 $p_k\times p_{l/r}$ ，然后推一下式子：

$$ \begin{align} f[k]&=\min_{w_l,w_r}\Biggl(\max\biggl(\max_{i\in L[k]}\{\sum_{j\in L[k]}k_jw_ld[A(i,j)]+\sum_{j\in R[k]}k_jw_rd[k]\},\max_{i\in R[k]}\{\sum_{j\in R[k]}k_jw_rd[A(i,j)]+\sum_{j\in L[k]}k_jw_ld[k]\}\biggr)\Biggr)\\ &=\min_{w_l,w_r}\Biggl(\max\biggl(\max_{i\in L[k]}\{\sum_{j\in L[k]}k_jw_ld[A(i,j)]\}+\sum_{j\in R[k]}k_jw_rd[k],\max_{i\in R[k]}\{\sum_{j\in R[k]}k_jw_rd[A(i,j)]\}+\sum_{j\in L[k]}k_jw_ld[k]\biggr)\Biggr)\\ &=\min_{w_l,w_r}\Biggl(\max\biggl(w_l\max_{i\in L[k]}\{\sum_{j\in L[k]}k_jd[A(i,j)]\}+w_r\sum_{j\in R[k]}k_jd[k],w_r\max_{i\in R[k]}\{\sum_{j\in R[k]}k_jd[A(i,j)]\}+w_l\sum_{j\in L[k]}k_jd[k]\biggr)\Biggr)\\ &=\min_{w_l,w_r}\Biggl(\max\biggl(w_lf[L[k]]+w_rd[k]\sum_{j\in R[k]}k_j,w_rf[R[k]]+w_ld[k]\sum_{j\in L[k]}k_j\biggr)\Biggr)\\ &=\min_{w_l,w_r}\Biggl(\max\biggl(w_lf[L[k]]+w_rd[k],w_rf[R[k]]+w_ld[k]\biggr)\Biggr)\\ &=\min_w\Biggl(\max\biggl(wf[L[k]]+(1-w)d[k],(1-w)f[R[k]]+wd[k]\biggr)\Biggr)\\ \end{align} $$

于是我们只要让 $w=\frac{f[R]-d[k]}{f[L]+f[R]-2d[k]}$ 就行了。

如果是多叉树的话就多叉转二叉即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 4000010

char c[MAXN];

int n;

struct node

{

    int tr[26];

    int maxl,par;

}s[MAXN];

int ptr = 1,root = 1,last = 1;

bool tag[MAXN];

int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

void extend(int k)

{

    int p = last;

    int np = newnode(s[p].maxl + 1);

    for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

    if(p == 0)s[np].par = root;

    else

    {

        int q = s[p].tr[k];

        if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

        else

        {

            int nq = newnode(s[p].maxl + 1);

            memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

            s[nq].par = s[q].par;

            s[q].par = s[np].par = nq;

            for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

        }

    }

    last = np;

    return;

}

struct edge

{

    int to,nxt;

}ve[MAXN];

int vedgenum = 0;

int vlin[MAXN] = {0};

void vadd(int a,int b)

{

    ve[++vedgenum] = (edge){b,vlin[a]};vlin[a] = vedgenum;

    return;

}

int tot;

edge e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{//cout << a << " => " << b << endl;

    e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

    return;

}

void rebuild(int k)

{

    int last = 0;

    for(int i = vlin[k];i != 0;i = ve[i].nxt)

    {//cout << k << " " << ve[i].to << endl;

        if(last == 0)

        {

            rebuild(ve[i].to);

            add(k,ve[i].to);

            last = k;

        }

        else

        {

            add(last,++tot);

            s[tot].maxl = s[k].maxl;

            add(tot,ve[i].to);

            last = tot;

            rebuild(ve[i].to);

        }

    }

    return;

}

double f[MAXN];

void dp(int k)

{

    if(tag[k]){f[k] = s[k].maxl;return;}

    int lc = 0,rc = 0;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(lc == 0)lc = e[i].to;

        else rc = e[i].to;

    }

    if(rc == 0)

    {

        dp(lc);

        f[k] = f[lc];

        return;

    }

    dp(lc);dp(rc);

    double w = (f[rc] - s[k].maxl) / (f[lc] + f[rc] - 2 * s[k].maxl);

    f[k] = w * (f[lc] - s[k].maxl) + s[k].maxl;

    return;

}

int main()

{

    scanf("%s",c + 1);

    n = strlen(c + 1);

    for(int i = n;i >= 1;--i)extend(c[i] - 'a'),tag[last] = 1;

    for(int i = 2;i <= ptr;++i)vadd(s[i].par,i);

    tot = ptr;

    rebuild(root);

    dp(root);

    printf("%.6lf\n",f[root]);

    return 0;

}