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

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, k, ans = INT_MAX;
        cin >> n >> k;
        vector<int> deep(n + 1), mDeep(n + 1);
        set<int> mark;
        vector<vector<int>> edge(n + 1);
        for (int i = 0; i < k; ++i) {
            int tmp;
            cin >> tmp;
            mark.insert(tmp);
        }
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        if (n == 1) {
            cout << 0 << endl;
            continue;
        }
        function<void(int, int)> dfs1 = [&](int x, int p) {
            for (auto &i: edge[x]) {
                if (p == i) continue;
                deep[i] = deep[x] + 1;
                dfs1(i, x);
            }
            mDeep[x] = mark.count(x) ? 0 : INT_MIN;
            for (auto &i: edge[x]) {
                if (p == i) continue;
                mDeep[x] = max(mDeep[x], mDeep[i] + 1);
            }
        };
        function<void(int, int, int)> dfs2 = [&](int x, int p, int v) {
            ans = min(ans, max(v, mDeep[x]));
            if (edge[x].size() == 1 && p != -1) return;
            if (p != -1 && edge[x].size() == 2) {
                dfs2(edge[x][0] == p ? edge[x][1] : edge[x][0], x, mark.count(x) ? max(v + 1, 1) : v + 1);
                return;
            }
            if (p == -1 && edge[x].size() == 1) {
                dfs2(edge[x][0], x, mark.count(x) ? max(v + 1, 1) : v + 1);
                return;
            }
            sort(edge[x].begin(), edge[x].end(), [&](const int &u, const int &v) {
                if (u == p) return false;
                if (v == p) return true;
                return mDeep[u] > mDeep[v];
            });
            int base = mark.count(x) ? 1 : INT_MIN;
            for (int i = 0; i < edge[x].size() - 1; ++i)
            dfs2(edge[x][i], x, max(base, max(v, mDeep[(i == 0 ? edge[x][1] : edge[x][0])] + 1) + 1));
        };
        deep[1] = 0;
        dfs1(1, -1);
        dfs2(1, -1, INT_MIN);
        cout << ans << endl;
    }
}

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
139
140
141
142
143
144
145

struct SegTree {
    vector<int> data1, data2, data3, data4, lazy;
    vector<bool> flag;
    int atom;
    explicit SegTree(int n) : data1((n << 1) + 10), data2((n << 1) + 10),
    data3((n << 1) + 10), data4((n << 1) + 10),
    lazy((n << 1) + 10), flag((n << 1) + 10, false), atom(-1) {}
    static inline int get(int l, int r) {
        return (l + r) | (l != r);
    }
    void up(int l, int r) {
        if (l == r) return;
        int mid = (l + r) >> 1;
        int cur = get(l, r), lx = get(l, mid), rx = get(mid + 1, r);
        flag[cur] = flag[lx] || flag[rx];
        data1[cur] = data1[lx];
        data2[cur] = data2[lx];
        data3[cur] = data3[rx];
        data4[cur] = data4[rx];
        if (data2[cur] < 0) data2[cur] = data1[rx];
        if (data3[cur] < 0) data3[cur] = data4[lx];
        if (flag[cur]) return;
        if (data4[lx] == data1[rx] || data4[lx] == data2[rx] || data3[lx] == data1[rx]) flag[cur] = true;
        else flag[cur] = false;
    }
    void build(int l, int r) {
        int cur = get(l, r);
        lazy[cur] = 0;
        if (l == r) {
            data2[cur] = atom--;
            data3[cur] = atom--;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid);
        build(mid + 1, r);
        up(l, r);
    }
    void push(int l, int r) {
        int cur = get(l, r);
        if (!lazy[cur]) return;
        int mid = (l + r) >> 1;
        int lx = get(l, mid), rx = get(mid + 1, r);
        data1[lx] = (data1[lx] + lazy[cur]) % 26;
        data2[lx] = data2[lx] < 0 ? data2[lx] : (data2[lx] + lazy[cur]) % 26;
        data3[lx] = data3[lx] < 0 ? data3[lx] : (data3[lx] + lazy[cur]) % 26;
        data4[lx] = (data4[lx] + lazy[cur]) % 26;
        lazy[lx] = (lazy[lx] + lazy[cur]) % 26;
        data1[rx] = (data1[rx] + lazy[cur]) % 26;
        data2[rx] = data2[rx] < 0 ? data2[rx] : (data2[rx] + lazy[cur]) % 26;
        data3[rx] = data3[rx] < 0 ? data3[rx] : (data3[rx] + lazy[cur]) % 26;
        data4[rx] = (data4[rx] + lazy[cur]) % 26;
        lazy[rx] = (lazy[rx] + lazy[cur]) % 26;
        lazy[cur] = 0;
    }
    void update(int l, int r, int x, int y, int w) {
        if (l == x && y == r) {
            int cur = get(l, r);
            data1[cur] = (data1[cur] + w) % 26;
            data2[cur] = data2[cur] < 0 ? data2[cur] : (data2[cur] + w) % 26;
            data3[cur] = data3[cur] < 0 ? data3[cur] : (data3[cur] + w) % 26;
            data4[cur] = (data4[cur] + w) % 26;
            lazy[cur] = (lazy[cur] + w) % 26;
            return;
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) update(l, mid, x, y, w);
        else if (x > mid) update(mid + 1, r, x, y, w);
        else {
            update(l, mid, x, mid, w);
            update(mid + 1, r, mid + 1, y, w);
        }
        up(l, r);
    }
    bool query(int l, int r, int x, int y) {
        if (l == x && y == r) {
            return flag[get(l, r)];
        }
        push(l, r);
        int mid = (l + r) >> 1;
        if (y <= mid) return query(l, mid, x, y);
        else if (x > mid) return query(mid + 1, r, x, y);
        else {
            bool tmp = query(l, mid, x, mid) || query(mid + 1, r, mid + 1, y);
            if (tmp) return true;
            int lx = get(l, mid), rx = get(mid + 1, r);
            if (data4[lx] == data1[rx]) return true;
            if (x <= mid - 1 && data3[lx] == data1[rx]) return true;
            if (y > mid + 1 && data4[lx] == data2[rx]) return true;
        }
        return false;
    }
    void debug(int l, int r) {
        #ifdef ACM_LOCAL
        int cur = get(l, r);
        cerr << '[' << l << '-' << r << "]: " << flag[cur] << "\t"
        << (data1[cur] >= 0 ? char(data1[cur] + 'a') : ' ')
        << (data2[cur] >= 0 ? char(data2[cur] + 'a') : ' ')
        << (data3[cur] >= 0 ? char(data3[cur] + 'a') : ' ')
        << (data4[cur] >= 0 ? char(data4[cur] + 'a') : ' ') << endl;
        if (l == r) return;
        int mid = (l + r) >> 1;
        debug(l, mid);
        debug(mid + 1, r);
        #endif
    }
};
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, q;
        cin >> n >> q;
        string str;
        str.reserve(n);
        SegTree tree(n);
        cin >> str;
        for (int i = 0; i < n; ++i) tree.data4[(i + 1) << 1] = tree.data1[(i + 1) << 1] = (str[i] - 'a');
        tree.build(1, n);
        for (int i = 0; i < q; ++i) {
            int o, l, r, w;
            cin >> o >> l >> r;
            if (o == 1) {
                cin >> w;
                tree.update(1, n, l, r, w % 26);
            } else
            cout << (tree.query(1, n, l, r) ? "NO" : "YES") << endl;
        }
        tree.debug(1, n);
    }
}