树上启发式合并

强大的解决对于子树的询问问题。

有个英文名字叫 dsu on tree。

一种是基于重链剖分的,一种是基于set map的启发式合并的。

第一种就是先走轻边,再走重边,重边的不改回来,这样修改次数就是 $logn$ 次的。

第二种就是看set map的size,把size小的并到大的上。

 

600E - Lomsat gelral

模板题啦

分享图片
#include <bits/stdc++.h>
#define ll long long

const int N = 1e5 + 7;

int n, cc[N], col[N], son[N], sz[N], skip[N];
ll ans[N];
std::vector<int> G[N];

void dfs1(int u, int fa = 0) {
    sz[u] = 1;
    for (auto v: G[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

ll sum;
int cx;

void edt(int u, int fa, int k) {
    cc[col[u]] += k;
    if (k > 0 && cc[col[u]] >= cx) {
        if (cc[col[u]] > cx) 
            sum = 0, cx = cc[col[u]];
        sum += col[u];
    }
    for (auto v: G[u])
        if (v != fa && !skip[v])
            edt(v, u, k);
}

void dfs(int u, int fa = 0, bool kep = 0) {
    for (auto v: G[u]) 
        if (v != fa && v != son[u])
            dfs(v, u);
    if (son[u])
        dfs(son[u], u, 1), skip[son[u]] = 1;
    edt(u, fa, 1);
    ans[u] = sum;
    if (son[u])
        skip[son[u]] = 0;
    if (!kep)
        edt(u, fa, -1), cx = sum = 0;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) 
        scanf("%d", col + i);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1);
    dfs(1);
    for (int i = 1; i <= n; i++)
        printf("%lld%c", ans[i], " \n"[i == n]);
    return 0;
}
View Code

 

570D - Tree Requests

把询问离线,一些字母能组成回文串,即出现偶数次的字母不能超过一个,那么对每一个深度用一个26位的二进制数表示一个字母出现的奇偶性,记为 $cnt[dep]$ 即可。

分享图片
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N =  5e5 + 7;
std::vector<int> G[N];
std::vector<std::pii> que[N];
int cnt[N], n, m, dep[N], sz[N], son[N];
char s[N];
bool ans[N], skip[N];

void dfs1(int u, int d) {
    dep[u] = d;
    sz[u] = 1;
    for (auto v: G[u]) {
        dfs1(v, d + 1);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

void edt(int u) {
    cnt[dep[u]] ^= (1 << (s[u] - a));
    for (auto v: G[u]) 
        if (!skip[v]) edt(v);
}

bool check(int d) {
    int res = 0;
    for (int i = 0; i < 26; i++)
        if (cnt[d] >> i & 1)
            res++;
    return res <= 1;
}

void dfs(int u, int keep = 0) {
    for (auto v: G[u])
        if (v != son[u]) dfs(v, 0);
    if (son[u])
        dfs(son[u], 1), skip[son[u]] = 1;
    edt(u);
    for (auto p: que[u])
        ans[p.se] = check(p.fi);
    if (son[u]) skip[son[u]] = 0;
    if (!keep)
        edt(u);
}

int main() {
//    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; i++) {
        int x;
        scanf("%d", &x);
        G[x].push_back(i);
    }
    scanf("%s", s + 1);
    for (int i = 1, u, h; i <= m; i++) {
        scanf("%d%d", &u, &h);
        que[u].push_back(std::pii(h, i));
    }
    dfs1(1, 1);
    dfs(1);
    for (int i = 1; i <= m; i++)
        puts(ans[i] ? "Yes" : "No");
    return 0;
}
View Code

 

Sgu507

想用重链剖分的写法。用一个multiset维护出现的数字,一个multiset维护每个插入的数和附近两个数的差值.

但是这跟插入顺序有关,插入的时候正着插入,删除的时候倒着删除,然后WA on 20了... 正着删除有RE on 20了...

看了一下别人的解法就是,每个结点维护一个set,发现这个set元素个数最多是所有叶子个数,空间能接受,然后就启发式合并就OK了。

分享图片
#include <bits/stdc++.h>

namespace IO {
    void read() {}
    template <typename T, typename... T2>
    inline void read(T &x, T2 &... oth) {
        T f = 1; x = 0;
        char ch = getchar();
        while (!isdigit(ch)) { if (ch == -) f = -1; ch = getchar(); }
        while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getchar(); }
        x *= f;
        read(oth...);
    }
} // using namespace IO
#define read IO::read
#define print IO::print
#define flush IO::flush

const int N = 1e5 + 7;
const int INF = 2147483647;
std::vector<int> vec[N];
std::set<int> st[N];
int n, m, color[N], ans[N];

int merge(int u, int v) {
    if (st[u].size() < st[v].size())
        std::swap(st[u], st[v]);
    int res = INF;
    for (std::set<int>::iterator it = st[v].begin(); it != st[v].end(); it++) {
        auto i = st[u].lower_bound(*it);
        if (i == st[u].begin()) {
            res = std::min(res, *i - *it);
        } else if (i == st[u].end()) {
            i--;
            res = std::min(res, *it - *i);
        } else {
            res = std::min(res, *i - *it);
            i--;
            res = std::min(res, *it - *i);
        }
        st[u].insert(*it);
    }
    st[v].clear();
    return res;
}

void dfs(int u) {
    ans[u] = INF;
    if (vec[u].size() == 0) {
        st[u].insert(color[u]);
        return;
    }
    for (int v: vec[u]) {
        dfs(v);
        ans[u] = std::min(ans[u], ans[v]);
        ans[u] = std::min(ans[u], merge(u, v));
    }
}

int main() {
    read(n, m);
    for (int i = 2; i <= n; i++) {
        int u;
        read(u);
        vec[u].push_back(i);
    }
    for (int i = n - m + 1; i <= n; i++)
        read(color[i]);
    dfs(1);
    for (int i = 1; i <= n - m; i++)
        printf("%d%c", ans[i], " \n"[i == n - m]);
    return 0;
}
View Code

 

HackerEarth, The Grass Type

这个就是每个结点维护一个map表示其子树钟出现过的数字以及出现的次数。

然后根据合并前枚举小的map里面的每个元素,看看大的map中能与其相乘成为当前结点的值的就行了。

分享图片
#include <bits/stdc++.h>
#define ll long long

const int N = 1e5 + 7;
std::map<int, int> mp[N];
int n, val[N];
std::vector<int> vec[N];
ll ans;

void merge(int u, int v) {
    if (mp[u].size() < mp[v].size()) std::swap(mp[u], mp[v]);
    for (auto p: mp[v]) {
        if (val[u] % p.first == 0)
            ans += 1LL * p.second * mp[u][val[u] / p.first];
    }
    for (auto p: mp[v]) 
        mp[u][p.first] += p.second;
    mp[v].clear();
}

void dfs(int u, int fa) {
    mp[u][val[u]] = 1;
    for (int v: vec[u]) {
        if (v == fa) continue;
        dfs(v, u);
        merge(u, v);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        scanf("%d", val + i);
    dfs(1, 0);
    printf("%lld\n", ans);
    return 0;
}
View Code

 

246E - Blood Cousins Return

对每一个深度用一个map维护出现的字符串以及出现的次数,然后然后就做完了。

分享图片
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N = 1e5 + 7;
char s[N][22];
std::vector<int> vec[N];
std::vector<std::pii> query[N];
std::map<std::string, int> mp[N];
int n, son[N], sz[N], dep[N], ans[N], root, cnt[N];
bool skip[N];

void dfs1(int u, int d) {
    sz[u] = 1;
    dep[u] = d;
    son[u] = -1;
    for (int v: vec[u]) {
        dfs1(v, d + 1);
        sz[u] += sz[v];
        if (son[u] == -1 || sz[son[u]] < sz[v]) son[u] = v;
    }
}

void edt(int u, int k) {
    mp[dep[u]][s[u]] += k;
    int w = mp[dep[u]][s[u]];
    if (k == 1 && w == 1) cnt[dep[u]]++;
    if (k == -1 && w == 0) cnt[dep[u]]--;
    assert(cnt[dep[u]] >= 0);
    for (int v: vec[u])
        if (!skip[v])
            edt(v, k);
}

void dfs(int u, bool keep = 0) {
    for (int v: vec[u])
        if (v != son[u])
            dfs(v);
    if (son[u] != -1)
        dfs(son[u], 1), skip[son[u]] = 1;
    edt(u, 1);
    for (auto p: query[u]) 
        ans[p.se] = cnt[dep[u] + p.fi];
    if (son[u] != -1)
        skip[son[u]] = 0;
    if (!keep)
        edt(u, -1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u; i <= n; i++) {
        scanf("%s%d", s[i], &u);
        vec[u].push_back(i);
    }
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int u, k;
        scanf("%d%d", &u, &k);
        query[u].push_back(std::pii(k, i));
    }
    dfs1(0, 0);
    dfs(0, 1);
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}
View Code

 

208E - Blood Cousins

先转换一下询问,把 $v_i$ 往上跳 $p_i$ 步得到 $u_i$,变成询问 $u_i$ 有多少个 $p_i$ 级儿子。然后就做完了。

分享图片
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second

const int N = 1e5 + 7;
int dep[N], son[N], sz[N], n, fa[N][20], ans[N];
bool skip[N];
std::vector<int> vec[N];
std::vector<std::pii> query[N];

void dfs1(int u, int pre = 0, int d = 0) {
    dep[u] = d;
    fa[u][0] = pre;
    for (int i = 1; i <= 18; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
        if (!fa[u][i]) break;
    }
    sz[u] = 1;
    son[u] = -1;
    for (int v: vec[u]) {
        dfs1(v, u, d + 1);
        sz[u] += sz[v];
        if (son[u] == -1 || sz[son[u]] < sz[v])
            son[u] = v;
    }
}

int jump(int u, int k) {
    for (int i = 18; ~i; i--)
        if (k >> i & 1)
            u = fa[u][i];
    return u;
}

int cnt[N];

void edt(int u, int k) {
    cnt[dep[u]] += k;
    for (int v: vec[u])
        if (!skip[v])
            edt(v, k);
}

void dfs(int u, bool keep = 0) {
    for (int v: vec[u])
        if (v != son[u])
            dfs(v);
    if (son[u] != -1) 
        dfs(son[u], 1), skip[son[u]] = 1;
    edt(u, 1);
    for (auto p: query[u]) {
        ans[p.se] = cnt[dep[u] + p.fi] - 1;
    }
    if (son[u] != -1)
        skip[son[u]] = 0;
    if (!keep)
        edt(u, -1);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int u;
        scanf("%d", &u);
        vec[u].push_back(i);
    }
    int m;
    scanf("%d", &m);
    dfs1(0);
    for (int i = 1; i <= m; i++) {
        int u, k;
        scanf("%d%d", &u, &k);
        u = jump(u, k);
        if (u) query[u].push_back(std::pii(k, i));
    }
    dfs(0, 1);
    for (int i = 1; i <= m; i++)
        printf("%d%c", ans[i], " \n"[i == m]);
    return 0;
}
View Code

 

待续...

相关文章
相关标签/搜索