QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#865024 | #5418. Color the Tree | CarroT1212 | RE | 1ms | 20304kb | C++14 | 2.0kb | 2025-01-21 13:58:57 | 2025-01-21 13:58:58 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=1e5+7,K=18;
ll n,a[N],dep[N],ans;
ll dfn[N],cnn,fa[N][K],dp[N];
ll m,b[N*2];
vector<ll> e[N],de[N],e1[N];
struct st {
ll mn[K][N];
void ini(ll n,ll *a) {
for (ll i=1;i<=n;i++) mn[0][i]=a[i];
for (ll i=1;i<K;i++) for (ll j=1;j+(1ll<<i)-1<=n;j++)
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1ll<<(i-1))]);
}
ll que(ll l,ll r) {
return min(mn[__lg(r-l+1)][l],mn[__lg(r-l+1)][r-(1ll<<__lg(r-l+1))+1]);
}
} T;
void dfs(ll p,ll f) {
dfn[p]=++cnn,dep[p]=dep[f]+1,fa[p][0]=f;
for (ll i=1;i<K;i++) fa[p][i]=fa[fa[p][i-1]][i-1];
for (ll i:e[p]) if (i!=f) dfs(i,p);
}
ll lca(ll x,ll y) {
if (dep[x]<dep[y]) swap(x,y);
for (ll i=K-1;~i;i--) if (dep[x]-dep[y]>=1ll<<i) x=fa[x][i];
if (x==y) return x;
for (ll i=K-1;~i;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void dfs1(ll p,ll f,ll d) {
dp[p]=0;
for (ll i:e1[p]) if (i!=f) dfs1(i,p,d),dp[p]+=dp[i];
ll w=T.que(d-dep[p]+1,d-dep[f]);
if (!dp[p]) dp[p]=w;
else dp[p]=min(dp[p],w);
}
void solve(ll d) {
b[m=1]=1; for (ll i:de[d]) b[++m]=i;
for (ll i=1;i<=m;i++) b[m+i]=lca(b[i],b[i+1]);
m=m*2-1,sort(b+1,b+m+1,[](ll x,ll y){return dfn[x]<dfn[y];});
m=unique(b+1,b+m+1)-1-b;
for (ll i=2;i<=m;i++) {
ll x=lca(b[i-1],b[i]);
e1[x].pb(b[i]),e1[b[i]].pb(x);
}
dfs1(1,0,d);
ans+=dp[1];
for (ll i=1;i<=m;i++) e1[b[i]].clear();
}
void mian() {
scanf("%lld",&n),ans=cnn=0;
for (ll i=1;i<=n;i++) scanf("%lld",&a[i]),e[i].clear(),de[i].clear();
T.ini(n,a);
for (ll i=1,x,y;i<n;i++) scanf("%lld%lld",&x,&y),e[x].pb(y),e[y].pb(x);
dfs(1,0);
for (ll i=1;i<=n;i++) de[dep[i]].pb(i);
for (ll i=1;i<=n;i++) if (de[i].size()) solve(i);
cout<<ans<<"\n";
}
bool ORY; int main() {
// while (1)
int t; for (scanf("%d",&t);t--;)
mian();
cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 20304kb
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
Runtime Error
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...