QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#534519#7513. Palindromic Beadsly_xxysML 0ms0kbC++205.2kb2024-08-27 13:20:212024-08-27 13:20:21

Judging History

你现在查看的是最新测评结果

  • [2024-08-27 13:20:21]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [2024-08-27 13:20:21]
  • 提交

answer

//#pragma GCC otimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+11;

struct Node {
    int Max = 0;
    Node *l = nullptr, *r = nullptr;
};
struct Tree {
    vector <Node> info;
    int tot = 0;
    Tree(){
        info.resize(N*150);
    }
    Node *open(){
        return &info[tot++];
    }
    void modify(Node *&u, int pl, int pr, int pos, int v){
        if (!u) u = open();
        u->Max = max(u->Max, v);
        if (pl == pr)return;
        int mid = (pl + pr) >> 1;
        if (mid >= pos){
            modify(u->l, pl, mid, pos, v);
        } else {
            modify(u->r, mid+1, pr, pos, v);
        }
    }
    int query(Node *u, int pl, int pr, int l, int r){
        if (pl >= l && pr <= r){
            return u->Max;
        }
        int mid = (pl + pr) >> 1;
        int Max = 0;
        if (u->l && mid >= l) Max = query(u->l, pl, mid, l, r);
        if (u->r && mid < r) Max = max(Max, query(u->r, mid+1, pr, l, r));
        return Max;
    }
};
struct order {
    int st, ed;
};

void solve(){
    int n;
    cin >> n;
    vector <vector<int>> g(n), st(n, vector<int>(19)), pairs(n);
    vector <int> dep(n), color(n);
    vector <order> ords(n);
    for (auto &x : color) cin >> x, x -= 1;
    for (int i = 0, a, b; i < n-1; ++ i){
        cin >> a >> b;
        -- a, -- b;
        g[a].push_back(b), g[b].push_back(a);
    }

    // 求lca部分
    int tot = 0;
    function <void(int,int)> dfs = [&](int x, int fa){
        ords[x].st =  tot ++;
        st[x][0] = fa;
        for (int i = 1; 1<<i <= dep[x]; ++ i)
            st[x][i] = st[st[x][i-1]][i-1];
        pairs[color[x]].push_back(x);
        for (auto &y : g[x]){
            if (y == fa) continue;
            dep[y] = dep[x] + 1;
            dfs(y, x);
        }
        ords[x].ed = tot-1;
    };

    auto lca = [&](int x, int y)->int{
        if (dep[x] < dep[y]) swap(x, y);
        for (int k=0, d=dep[x]-dep[y]; 1<<k <= d; ++ k)
            if (d>>k & 1) x = st[x][k];
        if (x == y) return x;
        for (int k=log2(dep[x]); k >= 0; -- k)
            if (st[x][k] != st[y][k]) x = st[x][k], y = st[y][k];
        return st[x][0];
    };

    auto Dis = [&](int x, int y)->int{
        int anc = lca(x, y);
        return dep[x] + dep[y] - 2*dep[anc];
    };

    dfs(0, 0);
    assert(tot == n);
    vector <array<int,3>> fs;
    for (int i = 0; i < n; ++ i){
        if (pairs[i].size() == 2){
            int u = pairs[i][0], v = pairs[i][1];
            fs.push_back({u, v, Dis(pairs[i][0], pairs[i][1])});
        }
    }
    sort(fs.begin(), fs.end(), [&](array <int,3> &a, array <int, 3> &b){
        return a[2] > b[2];
    });
    // 外层线段树
    vector <Node*> root(4*n);
    Tree Y;
    function<void(int,int,int,int,int,int)> modify = [&](int u, int pl, int pr, int x, int y, int v){
        Y.modify(root[u], 0, n-1, y, v);
        if (pl == pr) return;
        int mid = (pl + pr) >> 1;
        if (mid >= x) modify(2*u, pl, mid, x, y, v);
        else modify(2*u+1, mid+1, pr, x, y, v);
    };
    function<int(int,int,int,int,int,int,int)> ask = [&](int u, int pl, int pr, int l1, int r1, int l2, int r2){
        if (l1 > r1 || l2 > r2) return 0;
        if (pl >= l1 && pr <= r1){
            if (!root[u]) return 0;
            else return Y.query(root[u], 0, n-1, l2, r2);
        }
        int mid = (pl + pr) >> 1, Max = 0;
        if (root[2*u] && mid >= l1) Max = ask(2*u, pl, mid, l1, r1, l2, r2);
        if (root[2*u+1] && mid < r1) Max = max(Max, ask(2*u+1, mid+1, pr, l1, r1, l2, r2));
        return Max;
    };

    vector <int> f(fs.size());
    // 查询 + dp 部分

    for (int i = 0; i < fs.size(); ++ i){
        auto &[u, v, d] = fs[i];
        int ord1, ord2, ord3, ord4;
        assert(ords[u].st < ords[v].st);
        int anc = lca(u, v);
        // 根据 u 是否是 v 的祖先, 讨论 子路径的 情况
        if (anc == u){
            int lead = 0;
            for (auto &x : g[u]){
                if (Dis(x, v) == d-1){
                    lead = x;
                    break;
                }
            }
            // 小于 0 或者 大于 n-1 不影响结果
            ord1 = ords[lead].st-1, ord2 = ords[v].st, ord3 = ords[v].ed;
            f[i] = ask(1, 0, n-1, 0, ord1, ord2, ord3);
            ord1 = ords[v].st, ord2 = ords[v].ed, ord3 = ords[lead].ed+1;
            f[i] = max(f[i], ask(1, 0, n-1, ord1, ord2, ord3, n-1));
            f[i] += 2;
        } else {
            ord1 = ords[u].st, ord2 = ords[u].ed, ord3 = ords[v].st, ord4 = ords[v].ed;
            f[i] = ask(1, 0, n-1, ord1, ord2, ord3, ord4);
            f[i] += 2;
        }
        modify(1, 0, n-1, ords[u].st, ords[v].st, f[i]);
    }
    int res = 1;
    for (int i = 0; i < fs.size(); ++ i){
        int d = fs[i][2];
        if (d >= 2) ++ f[i];
        res = max(res, f[i]);
    }
    cout << res << "\n";
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int _ = 1;
    while (_--)
        solve();
    return 0;
}

/*
input:
4
1 1 2 2
1 2
2 3
2 4

5
1 3 2 2 1
1 2
2 3
3 4
4 5


output:

*/

詳細信息

Test #1:

score: 0
Memory Limit Exceeded

input:

4
1 1 2 2
1 2
2 3
2 4

output:

3

result: