QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#547855#5418. Color the TreeWuyanruWA 15ms20248kbC++143.2kb2024-09-05 11:30:132024-09-05 11:30:14

Judging History

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

  • [2024-09-05 11:30:14]
  • 评测
  • 测评结果:WA
  • 用时:15ms
  • 内存:20248kb
  • [2024-09-05 11:30:13]
  • 提交

answer

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
template<const int N,const int M>
struct graph
{
	int head[N+5];
	int ww[M+5];
	int t[M+5];
	int x[M+5];
	int cntm;
	graph(){ cntm=1;}
	inline void clear(int n=N)
	{
		cntm=1;
		for(int i=1;i<=n;i++) head[i]=0;
	}
	inline void ad(int u,int v,int w=0)
	{
		cntm++;
		t[cntm]=v;
		x[cntm]=head[u];
		ww[cntm]=w;
		head[u]=cntm;
	}
	inline void add(int u,int v,int w=0)
	{
		ad(u,v,w);
		ad(v,u,w);
	}
	inline int st(int num){ return head[num];}
	inline int to(int num){ return t[num];}
	inline int nx(int num){ return x[num];}
	inline int w(int num){ return ww[num];}
};
graph<100000,200000>g;
int st[21][100005];
int fa[21][100005];
vc<int>nod[100005];
int dep[100005];
int n;
inline void clear()
{
	g.clear(n);
	for(int i=1;i<=n;i++) nod[i].clear();
}
void dfs(int num)
{
	nod[dep[num]].push_back(num);
	for(int i=1;i<=16;i++) fa[i][num]=fa[i-1][fa[i-1][num]];
	for(int i=g.st(num);i;i=g.nx(i))
	{
		int p=g.to(i);
		if(p==fa[0][num]) continue;
		fa[0][p]=num,dep[p]=dep[num]+1,dfs(p);
	}
}
inline ll get(int l,int r)
{
	int num=31-__builtin_clz(r-l+1);
	// printf("get %d ~ %d : %d\n",l,r,min(st[num][l],st[num][r-(1<<num)+1]));
	return min(st[num][l],st[num][r-(1<<num)+1]);
}
inline int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=16;i>=0;i--) if(dep[u]-(1<<i)>=dep[v]) u=fa[i][u];
	if(u==v) return u;
	for(int i=16;i>=0;i--) if(fa[i][u]!=fa[i][v]) u=fa[i][u],v=fa[i][v];
	return fa[0][u];
}
ll dp[100001];
int sta[100001],top;
inline ll get(int D)
{
	int lst=0;dp[0]=0;assert(!top);
	for(int i:nod[D])
	{
		dp[i]=inf;
		if(!lst){ lst=sta[++top]=i;continue;}
		int p=lca(lst,i);lst=i;

		// printf("i=%d top=%d\n",i,sta[top]);
		while(top&&dep[sta[top]]>dep[p])
		{
			int t=sta[top--];
			int f=top?sta[top]:p;
			dp[t]=min(dp[t],get(D-dep[t],D-dep[f]-1));
			// printf("dp[%d]=%lld (f=%d)\n",t,dp[t],f);
			dp[f]+=dp[t];dp[t]=0;
		}
		if(sta[top]!=p) sta[++top]=p;
		sta[++top]=i;
	}
	while(top)
	{
		int t=sta[top--],f=sta[top];
		dp[t]=min(dp[t],get(D-dep[t],D-dep[f]-1));
		// printf("dp[%d]=%lld f=%d\n",t,dp[t],f);
		dp[f]+=dp[t];dp[t]=0;
	}
	// printf("D=%d : %lld\n",D,dp[0]);
	return dp[0];
}
inline void solve()
{
	clear();n=read();
	for(int i=0;i<n;i++) st[0][i]=read();
	for(int i=1;(1<<i)<=n;i++) for(int j=0;j+(1<<i)-1<n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	for(int i=1;i<n;i++) g.add(read(),read());
	dep[1]=1;dfs(1);ll ans=0;
	for(int i=1;nod[i].size();i++) ans+=get(i);
	printf("%lld\n",ans);
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}
/*
1
4
10 15 40 1
1 2
2 3
2 4
*/

详细

Test #1:

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

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: 15ms
memory: 20248kb

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:

185
177
222
230
156
255
225
126
100
81
155
73
159
134
155
152
228
230
140
195
155
171
78
282
195
286
191
211
119
206
211
247
88
252
239
244
173
180
195
131
109
149
180
182
226
210
182
97
226
59
56
31
115
224
203
172
155
208
53
158
189
187
173
137
233
106
163
273
80
350
156
133
172
159
240
269
156
22...

result:

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