QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212619#5418. Color the TreehazeWA 160ms3928kbC++204.1kb2023-10-13 18:20:562023-10-13 18:20:56

Judging History

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

  • [2023-10-13 18:20:56]
  • 评测
  • 测评结果:WA
  • 用时:160ms
  • 内存:3928kb
  • [2023-10-13 18:20:56]
  • 提交

answer

#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(Abs(pp),Abs(qq)):(pp)/(qq))
#define ll long long
#define LL __int128
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
	char ch = getchar();
	ll s = 0; bool w = 0;
	while(!isdigit(ch)){if(ch == '-')w = 1;ch = getchar();}
	while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return w ? - s : s;
}

const int itinf = 1e9;
const ll llinf = 4e18;
const int mod = 1000000007;
const int N = 500009;

inline int mul(int nma, int nmb){
	return ((1ll * nma * nmb % mod) + mod) % mod;
}

void solve(){
	int n = read(), lst = 0;
	ll ans = 0;
	vector<ll>c(n), dp(n), dfn(n);
	vector<vector<int>>g(n), dset(n);
	vector<array<int, 24>>fa(n), minc(n);
	irep(i,0,n - 1)c[i] = minc[i][0] = read();
	irep(i,1,n - 1){
		int u = read() - 1, v = read() - 1;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	auto dfs = [&](auto self, int x) -> void{
//		cerr << x << ' ' << endl;
		dfn[x] = lst ++;
		dset[dp[x]].push_back(x);
		for(int y : g[x]){
			if(y != 0 && dp[y] == 0){
				dp[y] = dp[x] + 1;
				fa[y][0] = x;
				self(self, y);
			}
		}
	};
		
	dfs(dfs, 0);
//	cerr << fa[3][0];
	for(int r = 1; r <= 23; ++ r){
		for(int i = 0; i < n; ++ i){
			fa[i][r] = fa[fa[i][r - 1]][r - 1];
			if((i + (1 << (r - 1))) > n)minc[i][r] = minc[i][r - 1];
			else minc[i][r] = min(minc[i][r - 1], minc[i + (1 << (r - 1))][r - 1]);
		}
	}
	
	auto rmq = [&](int l, int r) -> int{
		if(l > r)swap(l, r);
		int len = r - l + 1, pw = __lg(len);
		return min(minc[l][pw], minc[r - (1 << pw) + 1][pw]);
	};
	
	auto lca = [&](int x, int y) -> int{
		if(x == y)return x;
		if(dp[x] < dp[y])swap(x, y);
		for(int r = 23; r >= 0; -- r){
			if(dp[fa[x][r]] >= dp[y])x = fa[x][r];
		}
		if(x == y)return x;
		for(int r = 23; r >= 0; -- r){
			if(fa[x][r] != fa[y][r]){
				x = fa[x][r] , y = fa[y][r];
			}
		}
		return fa[x][0];
	};
	for(int i = 1; i < n; ++ i){
		if(dset[i].size()){
			dset[i].push_back(0);
			sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
		}
		else break;
		
		int sz = dset[i].size();
		for(int j = 0; j + 1 < sz; ++ j){
			dset[i].push_back(lca(dset[i][j], dset[i][j + 1]));
		}
		
		sort(dset[i].begin(), dset[i].end(), [&](int x,int y){return dfn[x] < dfn[y];});
		dset[i].erase(unique(dset[i].begin(), dset[i].end()), dset[i].end());

	//	cerr << "PRINT dset\n";
	//	for(int hh : dset[i])cerr << hh << ' ';
	//	cerr << endl;		
	
		vector<array<int, 2>>edge;
		vector<vector<int>>tree;
		sz = dset[i].size();
		map<int,int> idx, fd;

		for(int j = 0; j + 1 < sz; ++ j){
			int lc = lca(dset[i][j], dset[i][j + 1]);
			edge.push_back({lc, dset[i][j + 1]});
			if(idx.find(lc) == idx.end())
				idx[lc] = idx.size(), fd[idx[lc]] = dp[lc];
			if(idx.find(dset[i][j + 1]) == idx.end())
				idx[dset[i][j + 1]] = idx.size(),
				fd[idx[dset[i][j + 1]]] = dp[dset[i][j + 1]];
		}

		tree.resize(idx.size());

		for(auto [x, y] : edge){
			int u = idx[x], v = idx[y];
			tree[u].push_back(v);
			tree[v].push_back(u);
		//	cerr << u << ' ' << v << endl;
		}
	//	cerr << endl;
		vector<ll>f(idx.size(), llinf);
		auto work = [&](auto self, int x, int fax) -> void{
			/*
				i -> depth
				cost = a[depth - dp[u]] or sum f[v]
				i - (fd[u])
				i - (fd[fax] + 1)
			*/
			f[x] = rmq(i - fd[fax] - 1, i - fd[x]);
			if(i == fd[x]){
			//	f[x] = c[i - fd[x]];
				return;
			}

			ll alt = 0;
			for(int y : tree[x]){
				if(fd[y] > fd[x]){
					self(self, y, x);
					alt += f[y];
				}
			}
		//	cout << "Dt " << i - fd[x] <<  ' ' << f[x] << ' ' << alt << endl;;
			f[x] = min(f[x], alt);
			
			
		};
		work(work, 0, 0);
		ans += f[0];
	//	cout << "F= " << f[0] << endl;
	//	cout << endl;
	}
	//cout << endl;
	printf("%lld\n", ans + c[0]);
}

int main(){
	int T = read();
	while(T --){
		solve();
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3860kb

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
Wrong Answer
time: 160ms
memory: 3928kb

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:

146
113
189
201
148
225
211
115
100
79
155
68
143
108
142
110
196
198
116
168
138
126
78
218
182
245
152
176
88
153
157
205
71
247
212
193
158
170
152
116
96
116
165
163
221
183
155
91
149
59
56
22
115
182
186
122
121
185
50
105
155
136
159
119
205
78
152
219
80
318
145
116
118
147
197
231
107
177
9...

result:

wrong answer 1st numbers differ - expected: '180', found: '146'