QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#534507 | #7513. Palindromic Beads | ly_xxys | ML | 0ms | 0kb | C++23 | 5.2kb | 2024-08-27 12:57:27 | 2024-08-27 12:57:27 |
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*128);
}
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