QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#184382 | #5418. Color the Tree | Raiden | ML | 0ms | 17552kb | C++14 | 2.2kb | 2023-09-20 18:11:25 | 2023-09-20 18:11:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
vector<int> adj[MAX], nodes_in_depth[MAX], mono_ton;
int arr[MAX], dp[MAX], anc[20][MAX], lvl[MAX], st[MAX], T, ed[MAX];
void dfs(int u,int par = 0){
anc[0][u] = par, lvl[u] = lvl[par] + 1, nodes_in_depth[lvl[u]].push_back(u), st[u] = T++;
for(int j = 1; j < 20; j++) anc[j][u] = anc[j - 1][anc[j - 1][u]];
for(auto v : adj[u]){
if(v == par) continue;
dfs(v, u);
}
ed[u] = T;
}
int lca(int u,int v){
if(lvl[u] < lvl[v]) swap(u, v);
for(int j = 19; j >= 0; j--) if(lvl[u] - (1 << j) >= lvl[v]) u = anc[j][u];
if(u == v) return u;
for(int j = 19; j >= 0; j--) if(anc[j][u] != anc[j][v]) u = anc[j][u], v = anc[j][v];
return anc[0][u];
}
int is_a_ancestor_of_b(int a,int b){
return st[a] <= st[b] && st[b] < ed[a];
}
int f(int u,int dpth){
if(!adj[u].size()) return arr[*lower_bound(mono_ton.begin(), mono_ton.end(), dpth - lvl[u])];
long long ret = 0;
for(auto v : adj[u]){
ret += f(v, dpth);
}
return min((long long)arr[*lower_bound(mono_ton.begin(), mono_ton.end(), dpth - lvl[u])], ret);
}
int yo(vector<int> v,int dpth){
if(v.size() == 0) return 0;
int sz = v.size();
for(int i = 1; i < sz; i++) v.push_back(lca(v[i], v[i - 1]));
sort(v.begin(), v.end(), [&](int a, int b){ return st[a] < st[b];});
for(auto x : v) adj[x].clear();
stack<int> stk;
stk.push(v[0]);
for(int i = 1; i < v.size(); i++){
while(!is_a_ancestor_of_b(stk.top(), v[i])) stk.pop();
adj[stk.top()].push_back(v[i]);
stk.push(v[i]);
}
return f(v[0], dpth);
}
void solve(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> arr[i], adj[i + 1].clear(), nodes_in_depth[i + 1].clear();
mono_ton.clear();
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
adj[x].push_back(y), adj[y].push_back(x);
}
dfs(1);
long long ans = 0;
mono_ton.push_back(0);
for(int i = 1; i <= n; i++){
ans += yo(nodes_in_depth[i], i);
while(mono_ton.size() && arr[mono_ton.back()] > arr[i]) mono_ton.pop_back();
mono_ton.push_back(i);
}
cout << ans << '\n';
}
int32_t main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int t = 1;
cin >> t;
while(t--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 17552kb
input:
3 4 10 15 40 1 1 2 2 3 2 4 5 10 5 1 100 1000 1 2 2 3 2 4 4 5 4 1000 200 10 8 1 2 2 3 3 4
output:
35 17 1218
result:
ok 3 number(s): "35 17 1218"
Test #2:
score: -100
Memory Limit Exceeded
input:
3000 54 43 44 11 49 17 14 7 30 35 12 34 14 15 8 29 47 30 31 39 17 26 23 26 45 34 50 49 13 35 18 29 15 13 44 47 5 22 20 19 46 30 22 26 13 47 46 43 27 48 48 13 14 30 44 1 2 1 3 2 4 3 5 4 6 2 7 4 8 1 9 3 10 1 11 8 12 2 13 9 14 1 15 1 16 15 17 15 18 7 19 1 20 19 21 13 22 10 23 17 24 9 25 9 26 24 27 8 28...