欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ4598: [Sdoi2016]模式字符串(点分治 hash)

程序员文章站 2023-11-17 22:43:28
题意 "题目链接" Sol 直接考虑点分治+hash匹配 设$up[i]$表示$dep \% M = i$的从下往上恰好与前$i$位匹配的个数 $down$表示$dep \% M = i$的从上往下恰好与后$i$位匹配的个数 暴力转移即可 复杂度:$O(nlog^2n)??$ 代码写起来有一车边界 ......

题意

题目链接

sol

直接考虑点分治+hash匹配

\(up[i]\)表示\(dep \% m = i\)的从下往上恰好与前\(i\)位匹配的个数

\(down\)表示\(dep \% m = i\)的从上往下恰好与后\(i\)位匹配的个数

暴力转移即可

复杂度:\(o(nlog^2n)??\)

代码写起来有一车边界

#include<bits/stdc++.h>
#define ull unsigned long long 
#define ll long long 
#define int long long 
#define siz(v) ((int)v.size())
using namespace std;
const int maxn = 1e6 + 10, inf = 1e10 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, root, siz[maxn], mx[maxn], siz, dep[maxn], up[maxn], down[maxn], su[maxn], sd[maxn];
ll ans;
bool det[maxn];
char a[maxn], b[maxn];
vector<int> v[maxn];
ull hs[maxn], hp[maxn], po[maxn], base = 1331;
map<ull, bool> mp;
void findroot(int x, int fa) {
    siz[x] = 1; mx[x] = 0;
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa || det[to]) continue;
        findroot(to, x);
        siz[x] += siz[to]; mx[x] = max(mx[x], siz[to]);
    }
    mx[x] = max(mx[x], siz - siz[x]);
    if(mx[x] < mx[root]) root = x;
}
int dfs(int x, int fa, ull now) {
    siz[x] = 1;
    dep[x] = dep[fa] + 1;
    now = now * base + a[x];
    if(hp[dep[x]] == now) up[(dep[x] - 1) % m + 1]++, ans += sd[m - (dep[x] - 1) % m];
    if(hs[dep[x]] == now) down[(dep[x] - 1) % m + 1]++, ans += su[m - (dep[x] - 1) % m];
   // printf("%d %d\n", x, ans);
    int td =1;
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == fa || det[to]) continue;
        td = max(td, dfs(to, x, now) + 1); 
        siz[x] += siz[to];
    }
    return td;
}
void work(int x) {
    int tk = 0, tmp = 0;
    det[x] = 1; dep[x] = 1; su[1] = sd[1] = 1;//tag;
    for(int i = 0; i < siz(v[x]); i++) {   
        int to = v[x][i];   
        if(det[to]) continue;
        tk = min(m, dfs(to, x, a[x]) + 1), tmp = max(tmp, tk);
        for(int j = 1; j <= tk; j++) su[j] += up[j], sd[j] += down[j], up[j] = down[j] = 0;
    }
    for(int i = 1; i <= tmp; i++) su[i] = sd[i] = 0;
    for(int i = 0; i < siz(v[x]); i++) {
        int to = v[x][i];
        if(to == x || det[to]) continue;
        siz = siz[to]; root = 0; findroot(to, x); 
        work(root);
    }
}
void init() {
    for(int i = 1; i <= n; i++) v[i].clear();
    memset(det, 0, sizeof(det));
    memset(siz, 0, sizeof(siz));
    memset(mx, 0, sizeof(mx));
    ans = 0;    
}
void solve() {

    n = read(); m = read();
    init();
    scanf("%s", a + 1);
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) reverse(v[i].begin(), v[i].end());
    scanf("%s", b + 1); po[0] = 1;
    for(int i = 1; i <= n; i++) {
        hp[i] = hp[i - 1] + b[(i - 1) % m + 1] * po[i - 1];
        hs[i] = hs[i - 1] + b[m - (i - 1) % m] * po[i - 1];
        po[i] = base * po[i - 1];
    }
    siz = n; mx[0] = inf; root = 0; findroot(1, 0);
    work(1); 
    printf("%d\n", ans);
}
signed main() {
    freopen("a.in", "r", stdin);
    for(int t = read(); t; t--, solve());
    return 0;
}