제출 #1157157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157157		12345678	Sjekira (COCI20_sjekira)	C++20	110 / 110	174 ms	26648 KiB

sjekira

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, inf=1e9;

#define ll long long

ll n, u, v, t[nx], pa[nx], cnt, in[nx], out[nx], res, st, rid[nx];
vector<ll> d[nx];

void dfs(int u, int p)
{
    pa[u]=p;
    in[u]=++cnt;
    rid[cnt]=u;
    for (auto v:d[u]) if (v!=p) dfs(v, u);
    out[u]=cnt;
}

struct segtree
{
    ll lz[4*nx];
    pair<ll, int> d[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i].first+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void build(int l ,int r, int i)
    {
        if (l==r) return d[i]={t[rid[l]], rid[l]}, void();
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql ,qr ,vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
} s;

void solve(int u)
{
    //if (++st>=10) return;
    //cout<<"here "<<u<<' '<<in[u]<<' '<<out[u]<<' '<<res<<'\n';
    s.update(1, n, 1, 1, n, -inf);
    //cout<<"s "<<s.d[1].first<<' '<<s.d[1].second<<'\n';
    for (auto v:d[u])
    {
        if (v==pa[u]) continue;
        s.update(1, n, 1, in[v], out[v], inf);
        //cout<<"debugv "<<u<<' '<<s.d[1].first<<' '<<s.d[1].second<<'\n';
        if (s.d[1].first>0) res+=s.d[1].first+t[u], solve(s.d[1].second);
        s.update(1, n, 1, in[v], out[v], -inf);
    }
    if (pa[u]!=-1)
    {
        if (in[u]>1) s.update(1, n, 1, 1, in[u]-1, inf);
        if (out[u]<n) s.update(1, n, 1, out[u]+1, n, inf);
        //cout<<"debug "<<u<<' '<<s.d[1].first<<' '<<s.d[1].second<<'\n';
        if (s.d[1].first>0) res+=s.d[1].first+t[u], solve(s.d[1].second);
        if (in[u]>1) s.update(1, n, 1, 1, in[u]-1, -inf);
        if (out[u]<n) s.update(1, n, 1, out[u]+1, n, -inf);
    }
    s.update(1, n, 1, 1, n, inf);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>t[i];
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    dfs(1, -1);
    //for (int i=1; i<=n; i++) cout<<"rid "<<i<<' '<<rid[i]<<'\n';
    s.build(1, n, 1);
    solve(s.d[1].second);
    cout<<res;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60