省选模拟 19/10/22 Gosling (括号序列) (区间DP) (重链剖分思想优化)

​​传送门​​​ 看上去不可做…

两个树相同，可以转换为括号序列相同

看看操作在括号序列上的体现

1. 生长：在任意位置添加一个括号，费用为括号的权值 *
2. 伸展：在一个子树的两端填加括号，费用为括号权值 *
3. 收缩：删除一个括号
4. 转换：改一个括号的权值

最后需要让两颗树的括号序列相同

首先 1，2 操作都可以看做添括号，添括号相当于在另一边删括号

考虑 ，令 表示把区间 变成一样的最小代价

1. 删括号：枚举删哪个的括号，删左右的括号
2. 改权值：这个括号不能动了，递归处理括号内和括号外

复杂度

#include<bits/stdc++.h>
#define cs const
using namespace std;
int read(){
    int cnt = 0, f = 1; char ch = 0;
    while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1; }
    while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar();
    return cnt * f;
}
cs int N = 4e3 + 5, P = 3e7 + 7;
struct Graph{
    int first[N], nxt[N], to[N], w[N], tot;
    void add(int x, int y, int z){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z;}
    int lp[N], rp[N], seq[N], len;
    void dfs(int u){
        for(int i = first[u]; i; i = nxt[i]){
            int t = to[i];
            seq[++len] = i; lp[i] = len;
            dfs(t);
            seq[++len] = i; rp[i] = len;
        }
    }
}A, B;
int c1, c2, n1, n2;
typedef long long ll;
ll f[P], g[P]; 
ll hash(int l, int r, int u, int v){
    return r + 103ll * l + 103ll * 103ll * u + 103ll * 103ll * 4003ll * v;
}
int find(int l, int r, int u, int v){
    ll k = hash(l, r, u, v), p = k % P;
    while(g[p] && (g[p]^k)) p = (p + 1) % P;
    return p;
}
ll dp(int l, int r, int u, int v){
    while(l <= r && (A.rp[A.seq[l]] == l || A.rp[A.seq[l]] > r)) ++l;
    while(l <= r && (A.lp[A.seq[r]] == r || A.lp[A.seq[r]] < l)) --r;
    while(u <= v && (B.rp[B.seq[u]] == u || B.rp[B.seq[u]] > v)) ++u;
    while(u <= v && (B.lp[B.seq[v]] == v || B.lp[B.seq[v]] < u)) --v;
    int now = find(l, r, u, v);
    if(g[now]) return f[now];
    g[now] = hash(l, r, u, v);
    if(l > r){
        ll sum = 0;
        for(int i = u; i <= v; i++) if(B.lp[B.seq[i]] == i && B.rp[B.seq[i]] <= v) sum += 1ll * c1 * B.w[B.seq[i]]; 
        return f[now] = sum;
    }
    if(u > v){
        ll sum = 0;
        for(int i = l; i <= r; i++) if(A.lp[A.seq[i]] == i && A.rp[A.seq[i]] <= r) sum += 1ll * c1 * A.w[A.seq[i]];
        return f[now] = sum;
    }
    ll ret = 1e18, val;
    if(B.rp[B.seq[u]] - u <= v - B.lp[B.seq[v]]){
        val = dp(l + 1, A.rp[A.seq[l]] - 1, u + 1, B.rp[B.seq[u]] - 1) + dp(A.rp[A.seq[l]] + 1, r, B.rp[B.seq[u]] + 1, v);
        ret = min(ret, val + 1ll * c2 * abs(A.w[A.seq[l]] - B.w[B.seq[u]]));
        ret = min(ret, dp(l + 1, r, u, v) + 1ll * c1 * A.w[A.seq[l]]);
        ret = min(ret, dp(l, r, u + 1, v) + 1ll * c1 * B.w[B.seq[u]]);
    }
    else{
        val = dp(l, A.lp[A.seq[r]] - 1, u, B.lp[B.seq[v]] - 1) + dp(A.lp[A.seq[r]] + 1, r - 1, B.lp[B.seq[v]] + 1, v - 1);
        ret = min(ret, val + 1ll * c2 * abs(A.w[A.seq[r]] - B.w[B.seq[v]]));
        ret = min(ret, dp(l, r - 1, u, v) + 1ll * c1 * A.w[A.seq[r]]);
        ret = min(ret, dp(l, r, u, v - 1) + 1ll * c1 * B.w[B.seq[v]]);
    } return f[now] = ret;
}
int main(){
    c1 = read(), c2 = read();
    n1 = read();
    for(int i = 1; i <= n1; i++){
        int k = read();
        while(k--){
            int x = read(), w = read();
            A.add(i, x, w);
        }
    }
    n2 = read();
    for(int i = 1; i <= n2; i++){
        int k = read();
        while(k--){
            int x = read(), w = read();
            B.add(i, x, w);
        }
    } A.dfs(1); B.dfs(1);
    cout << dp(1, A.len, 1, B.len);
    return 0;
}