QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#129458#5418. Color the TreeAlinxesterRE 2ms24212kbC++144.0kb2023-07-22 19:48:092023-07-22 19:50:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-22 19:50:31]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:24212kb
  • [2023-07-22 19:48:09]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod 998244353
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l , r)(rng);}
template<typename T> inline void read (T &t) {
	t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
	while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
	while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
	if (ch == '.') {
		ch = getchar();
		while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
	}
	t = (f ? -t : t);
}
template <typename T, typename... Args>
	inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
	if (x >= 10) write(x / 10);
	cout << (ll) (x % 10);
}
const int N = 2e5 + 2, INF = 1e18 + 2;
int n, a[N], head[N], pos;
int ans;
struct Seg_tree {
	int tree[N << 2];
	inline void pushup (int rt) {
		tree[rt] = min(tree[rt << 1], tree[rt << 1 | 1]); }
	inline void build (int rt, int l, int r) {
		if (l == r) {
			tree[rt] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
		pushup(rt);
	}
	inline int query (int rt, int l, int r, int L, int R) {
		if (L <= l && r <= R) return tree[rt];
		int mid = (l + r) >> 1, ret = INF;
		if (L <= mid) ret = min(ret, query(rt << 1, l, mid, L, R));
		if (R > mid) ret = min(ret, query(rt << 1 | 1, mid + 1, r, L, R));
		return ret;
	}
}seg_tree;
struct Edge { int to, next; }edge[N << 1];
inline void add_edge (int u, int v) {
	edge[++pos] = (Edge) {v, head[u]}, head[u] = pos; }
int dfn[N], dfc, dep[N], son[N], mxdep[N], fath[N], top[N];
vector<pii > f[N];
inline void merge (int u, int v) {
	int size1 = (int)f[u].size(), size2 = (int)f[v].size();
	rep (i, 0, size2 - 1) {
		int d = size2 - i + dep[v] - 1, p = size1 + dep[u] - d - 1;
		f[u][p].fir = min(f[u][p].fir, seg_tree.query(1, 0, n - 1, d - f[u][p].sec, d - dep[u])) + min(f[v][p].fir, seg_tree.query(1, 0, n - 1, d - f[v][p].sec, d - dep[v]));
		f[u][p].sec = dep[u];
	}
}
inline void dfs1 (int u, int fa) {
	dep[u] = dep[fa] + 1, fath[u] = fa;
	go (i, u) {
		int v = edge[i].to;
		if (v == fa) continue;
		dfs1(v, u);
		if (dep[v] > mxdep[u]) son[u] = v, mxdep[u] = dep[v];
	}
}
inline void dfs2 (int u, int Top) {
	dfn[u] = ++dfc, top[u] = Top;
	go (i, u) {
		int v = edge[i].to;
		if (v == fath[u]) continue;
		if (son[u] == v) dfs2(v, Top);
		else dfs2(v, v);
	}
	if (!son[u]) f[u].emplace_back(MP(a[0], dep[u]));
	else {
		swap(f[u], f[son[u]]), f[son[u]].clear();
		f[u].emplace_back(MP(a[0], dep[u]));
		go (i, u) {
			int v = edge[i].to;
			if (v == fath[u] || v == son[u]) continue;
			merge(u, v), f[v].clear();
		}
	}
}
int T;
signed main() {
	read(T);
	while (T--) {
		memset(head, 0, sizeof head), memset(mxdep, 0, sizeof mxdep), memset(son, 0, sizeof son);
		ans = pos = dfc = 0;
		read(n);
		rep (i, 0, n - 1) read(a[i]);
		seg_tree.build(1, 0, n - 1);
		int u, v;
		rep (i, 1, n - 1) read(u, v), add_edge(u, v), add_edge(v, u);
		dfs1(1, 0), dfs2(1, 1);
		rep (i, 0, (int) f[1].size() - 1) {
			int d = (int) f[1].size() - i;
			ans += min(f[1][i].fir, seg_tree.query(1, 0, n - 1, d - f[1][i].sec, d - 1));
		}
		printf("%lld\n", ans);
	}
return 0;
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 24212kb

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
Dangerous Syscalls

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: