QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107655 | #5418. Color the Tree | gtm1514 | RE | 0ms | 0kb | C++14 | 2.8kb | 2023-05-22 11:38:42 | 2023-05-22 11:38:46 |
Judging History
answer
/*你说的对,但是大样例呢*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#define int long long
using namespace std;
int n,a[100010];
struct ST{
int st[100010][21];
void build(){
for(int i=0;i<n;i++)st[i][0]=a[i];
for(int j=1;j<__lg(n);j++){
for(int i=0;i+(1<<j)-1<n;i++){
st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
}
}
int query(int l,int r){
int k=__lg(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
}st;
struct node{
int v,next;
}edge[200010];
int t,head[100010];
void add(int u,int v){
edge[++t].v=v;edge[t].next=head[u];head[u]=t;
}
int dep[100010],son[100010],sec[100010];
void dfs1(int x,int f){
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f){
dfs1(edge[i].v,x);
if(dep[son[x]]<dep[edge[i].v])sec[x]=dep[son[x]],son[x]=edge[i].v;
else if(sec[x]<dep[edge[i].v])sec[x]=dep[edge[i].v];
}
}
sec[x]++;
dep[x]=dep[son[x]]+1;
}
int buf1[100010],*dp[100010],*now1=buf1;
int buf2[100010],*lz[100010],*now2=buf2;
void dfs2(int x,int f){
if(son[x]){
dp[son[x]]=dp[x]+1;lz[son[x]]=lz[x]+1;
dfs2(son[x],x);
}
dp[x][0]=a[0];
for(int i=head[x];i;i=edge[i].next){
if(edge[i].v!=f&&edge[i].v!=son[x]){
dp[edge[i].v]=now1;now1+=dep[edge[i].v];
lz[edge[i].v]=now2;now2+=dep[edge[i].v];
dfs2(edge[i].v,x);
for(int j=1;j<=dep[edge[i].v];j++){
dp[edge[i].v][j-1]=min(dp[edge[i].v][j-1],st.query(lz[edge[i].v][j-1],j-1));
dp[x][j]+=dp[edge[i].v][j-1];
}
}
}
for(int i=0;i<sec[x];i++)dp[x][i]=min(dp[x][i],a[i]);
for(int i=0;i<sec[x];i++)lz[x][i]=i+1;
}
void clear(){
t=0;
for(int i=0;i<=n;i++)head[i]=son[i]=dep[i]=sec[i]=buf1[i]=buf2[i]=0;
for(int i=0;i<=__lg(n);i++)for(int j=0;j<n;j++)st.st[j][i]=0;
now1=buf1;now2=buf2;
}
signed main(){
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
int tim=1;
scanf("%lld",&tim);
while(tim--){
scanf("%lld",&n);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
st.build();
for(int i=1;i<n;i++){
int u,v;scanf("%lld%lld",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
dp[1]=now1;now1+=dep[1];lz[1]=now2;now2+=dep[1];
dfs2(1,0);
int ans=0;
for(int i=0;i<sec[1];i++)ans+=dp[1][i];
for(int i=sec[1];i<dep[1];i++){
dp[1][i]=min(dp[1][i],st.query(lz[1][i],i));
ans+=dp[1][i];
}
printf("%lld\n",ans);
clear();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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