QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#547855 | #5418. Color the Tree | Wuyanru | WA | 15ms | 20248kb | C++14 | 3.2kb | 2024-09-05 11:30:13 | 2024-09-05 11:30:14 |
Judging History
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'