题目链接：https://contest.ucup.ac/contest/1511/problem/8213

题目大意：

给一个树，给一个长度不超过 $3$ 的串，然后问：每个点填一个字母，最大化满足经过的点构成的字符串等于给定串的有向路径数量，输出数量。

做法

显然只有长度为 $3$ 的串需要思考，当只有两个不同的字母的时候，会发现如果使用 $dp[x][0/1]$ 的 dp 方式，会无法处理从 $x$ 的儿子的儿子，到 $x$ 的路径，所以我们需要再多添加一维，表示父亲填的字母，相当于提前知道了父亲填的字母，然后父亲在转移的时候直接调用就行了。

但是会发现我们仍然无法处理三个字母都不同的情况，因为儿子有三种选择。

但是注意到第一个字母和第三个字母并没有本质区别，将一个子树的第一个字母和第三个字母全部颠倒不会影响这个子树的贡献，所以也就只需要知道儿子应该选一/三字母或者第二个字母就行，排个序枚举一下就行了。

时间复杂度：$O(n\log{n})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
const int N=3e5+5;
const int NN=6e5+5;
LL dp[N][4][4];
int ss[4],n,m,C;char st[10];
int vis[300];
struct node{
    int y,next;
}a[NN];int len,las[N];
void ins(int x,int y){a[++len]={y,las[x]};las[x]=len;}
bool pd(int x,int y){
    assert(m==2);
    return (x==ss[1] && y==ss[2]) || (x==ss[2] && y==ss[1]);
}
bool pd(int x,int y,int z){
    assert(m==3);
    return (x==ss[1] && y==ss[2] && z==ss[3]) || (x==ss[3] && y==ss[2] && z==ss[1]);
}
LL count(LL c1,LL c2,int fc){
    assert(C>1);
    LL tmp=0;
    if(C==2){
        if(pd(1,ss[2],1)==1)tmp+=c1*(c1-1)/2;
        // if(pd(2,ss[2],2)==1)tmp+=c2*(c2-1)/2; impossible
        if(pd(1,ss[2],2)==1)tmp+=c1*c2;
        if(pd(1,ss[2],fc)==1)tmp+=c1;
        if(pd(2,ss[2],fc))tmp+=c2;
    }
    else{
        if(fc==1 || fc==3){
            LL c3=(c1+1)/2;
            tmp+=c3*(c1-c3)+c3;
        }
        else{
            LL c3=c1/2;
            tmp+=c3*(c1-c3);
        }
    }
    return tmp;
}
LL sta[N];int top;
VI son[N];
void dfs(int x,int fa){
    for(int k=las[x];k;k=a[k].next){
        int y=a[k].y;if(y==fa)continue;
        son[x].push_back(y);
        dfs(y,x);
    }
    if(m==2){
        for(int i=1;i<=C;i++){
            LL now=0;
            for(auto y:son[x]){
                LL tmp=0;
                for(int j=1;j<=C;j++){
                    tmp=max(dp[y][i][j],tmp);
                }
                now+=tmp;
            }
            for(int fc=1;fc<=C;fc++){//father color
                if(x!=1 && pd(i,fc))dp[x][fc][i]=now+1;
                else dp[x][fc][i]=now;
            }
        }
    }
    else{//m=3
        assert(m==3);
        for(int i=1;i<=C;i++){
            if(i!=ss[2]){//only up
                LL now=0;
                for(auto y:son[x]){
                    LL tmp=0;
                    for(int j=1;j<=C;j++){
                        tmp=max(tmp,dp[y][i][j]);
                    }
                    now+=tmp;
                }
                for(int fc=1;fc<=C;fc++){//father color
                    dp[x][fc][i]=now;
                }
            }
            else if(C==1){
                LL siz=son[x].size();
                for(auto y:son[x]) dp[x][1][1]+=dp[y][1][1];
                dp[x][1][1]+=siz*(siz-1)/2;
                if(x!=1)dp[x][1][1]+=siz;
            }
            else{
                top=0;
                LL ini=0;
                for(auto y:son[x]){
                    sta[++top]=dp[y][i][2]-dp[y][i][1];
                    assert(C!=3 || dp[y][i][1]==dp[y][i][3]);
                    ini+=dp[y][i][1];
                }
                sort(sta+1,sta+top+1,[](LL x,LL y){return x>y;});
                for(int fc=1;fc<=C;fc++){
                    LL now=0,tmp=ini;
                    for(int j=0;j<=top;j++){
                        if(x!=1)now=max( now , tmp+count(top-j,j,fc) );
                        else now=max( now , tmp+count(top-j,j,0) );
                        if(j!=top) tmp+=sta[j+1];
                    }
                    dp[x][fc][i]=now;
                }
            }
        }
    }
}

LL work(){
    scanf("%d",&n);
    scanf("%s",st+1);m=strlen(st+1);
    for(int i=2;i<=n;i++){
        int x,y;scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    for(int i=1;i<=m;i++){
        if(!vis[st[i]])vis[st[i]]=++C;
        ss[i]=vis[st[i]];
    }
    if(m==1)return n;
    
    dfs(1,0);

    LL ans=0;
    for(int i=1;i<=C;i++)ans=max(ans,dp[1][1][i]);

    if(ss[1]==ss[m])ans*=2;

    return ans;
}
int main(){
    printf("%lld\n",work());
    return 0;
}

题外话：
其实这个 dp 设计非常有意思。

  1. 从树的角度考虑，我们其实有另外一种设计思路是，多添加几维表示这个节点的每个颜色的儿子选了多少个，但是可以发现这种设计是显然会超时的。

    这是因为一个节点的儿子数量可以很多，而父亲至多一个，因此，我们更希望通过父亲解决问题，而不是通过儿子。

    一个类似的例子是：一个数据结构题目，每次能够给一个点周围的所有点的点权加上 $c$ ，做法为：父亲的点权直接加上，儿子的点权加在自己身上，等查询一个点点权的时候让他自己来问父亲。

    当然，上面那个例子还有个单 log 做法，就是利用 BFS 序+线段树，因为 BFS 序上儿子的编号是连续的。

  2. 从预知未来的角度考虑：

    每个点先预知未来的一些信息，在这道题目上的作用是，让我们能够处理了一些本来无法处理的信息。

    当然也可以有其他作用，举个减少时间复杂度的例子（某一年提高组初赛的题目，忘记是哪一年了）：

    坑

    这道题目到底是哪一年的。

    求长度恰好为 $k$ 且相邻数字的异或的和最大的子序列，输出最大的和，值域 $2^{8}-1$。

    做法为 $dp[i][x][y]$ ，$i$ 是已经有几个数字，$x$ 表示子序列目前最后一个数字的上 $4$ 位，$y$ 表示我们期望下一个数字的下 $4$ 位是多少。

    这样就能在 $O(n^2*2^4)$ 的复杂度处理这个问题，相较于 $dp[i][x]$ 少了 $2^4$ 。