QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#184382#5418. Color the TreeRaidenML 0ms17552kbC++142.2kb2023-09-20 18:11:252023-09-20 18:11:26

Judging History

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

  • [2023-09-20 18:11:26]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:17552kb
  • [2023-09-20 18:11:25]
  • 提交

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...

output:


result: