QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139658 | #5418. Color the Tree | lefy | WA | 3ms | 12112kb | C++14 | 2.2kb | 2023-08-14 09:34:38 | 2023-08-14 09:34:40 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int a[N],dfn[N],tot,f[N][20],n,dep[N];
vector<int>e[N],d[N];
ll dp[N];
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
d[dep[x]].push_back(x);
f[x][0]=fa;
for(int i=1;i<=log2(n);i++)f[x][i]=f[f[x][i-1]][i-1];
dfn[x]=++tot;
for(int v:e[x])if(v!=fa)dfs(v,x);
}
int cmp(int x,int y){
return dfn[x]<dfn[y];
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=log2(n);i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
if(x==y)return x;
for(int i=log2(n);i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int st[N],top;
void insert(int x){
if(!top){
st[++top]=x;return;
}
int z=lca(x,st[top]);
while(top>1&&dep[st[top-1]]>dep[z]){
e[st[top-1]].push_back(st[top]);top--;
}
if(dep[st[top]]>dep[z])e[z].push_back(st[top]),top--;
if(!top||st[top]!=z)st[++top]=z;
st[++top]=x;
}
int Min[N][20];
ll get(int l,int r){
if(l>r)return 1e18;
int t=log2(r-l+1);
return min(Min[l][t],Min[r-(1<<t)+1][t]);
}
vector<int>t;
void dfs(int x,int fa,int D){
t.push_back(x);
ll sum=1e18;
for(int v:e[x]){
// cout<<x<<" "<<v<<"\n";
if(sum==1e18)sum=0;
dfs(v,x,D);sum+=dp[v];
}
dp[x]=min(get(D-dep[x]+1,D-dep[fa]),sum);
}
void solve(){
tot=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),Min[i][0]=a[i],d[i].clear();
for(int i=1;i<=log2(n);i++){
for(int j=1;j+(1<<i)-1<=n;j++)Min[j][i]=min(Min[j][i-1],Min[j+(1<<i-1)][i-1]);
}
for(int i=1;i<n;i++){
int x,y;scanf("%d%d",&x,&y);
e[x].push_back(y),e[y].push_back(x);
}
dfs(1,0);ll ans=0;
for(int i=1;i<=n;i++)e[i].clear(),dp[i]=0;
for(int i=n;i;i--)if(d[i].size()){
sort(d[i].begin(),d[i].end(),cmp);
if(d[i][0]!=1)insert(1);
for(int x:d[i])insert(x);
while(top>1)e[st[top-1]].push_back(st[top]),top--;top=0;
dfs(1,0,i);ans+=dp[1];
for(int x:t)e[x].clear(),dp[x]=0;
}
printf("%lld",ans);
}
int main() {
int t;scanf("%d",&t);
while(t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 12112kb
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:
35171218
result:
wrong answer 1st numbers differ - expected: '35', found: '35171218'