제출 #783194

#제출 시각아이디문제언어결과실행 시간메모리
783194KahouConstruction of Highway (JOI18_construction)C++14
0 / 100
2 ms2772 KiB
/* In the name of God, aka Allah */ #include<bits/stdc++.h> using namespace std; #define F first #define S second #define endl '\n' #define mk make_pair typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = 1e5 + 50, LG = 17; int n, a[N], f[N], h[N], st[N], ft[N], par[LG][N], fen[2][N], tim; pii P[N]; pii E[N]; vector<int> adj[N]; void dfs(int u) { st[u] = ++tim; for (int v:adj[u]) { h[v] = h[u]+1; par[0][v] = u; dfs(v); } ft[u] = tim; } int get(int c, int i) { int out = 0; for (; i > 0; i -= i&-i) out += fen[c][i]; return out; } void upd(int c, int i, int x) { for (; i <= n; i += i&-i) fen[c][i] += x; } int getpar(int u) { int tmp = get(0, st[u]); int v = u; for (int k = LG-1; k >= 0; k--) { if (tmp - get(0, st[par[k][v]]) == 0) v = par[k][v]; } return v; } void solve() { cin >> n; for (int u = 1; u <= n; u++) { cin >> a[u]; P[u] = {a[u], u}; } sort(P+1, P+n+1); int t = 0; for (int i = 1; i <= n; i++) { if (P[i].F != P[i-1].F) t++; a[P[i].S] = t; } for (int i = 1; i <= n-1; i++) { int u, v; cin >> u >> v; E[i] = {u, v}; adj[u].push_back(v); } h[1] = 1; dfs(1); for (int k = 1; k < LG; k++) { for (int u = 1; u <= n; u++) { par[k][u] = par[k-1][par[k-1][u]]; } } upd(0, st[1], +1); upd(0, ft[1]+1, -1); for (int i = 1; i <= n-1; i++) { int u = E[i].F; ll out = 0; while (u) { int v = getpar(u); upd(1, a[u], h[u]-h[v]+1); out += 1ll*(h[u]-h[v]+1)*get(1, a[u]-1); u = par[0][v]; } cout << out << endl; u = E[i].F; if (f[u]) { upd(0, st[f[u]], +1); upd(0, ft[f[u]]+1, -1); } f[u] = E[i].S; while (u) { int v = getpar(u); upd(1, a[u], -(h[u]-h[v]+1)); a[u] = a[E[i].S]; if (v != 1) { upd(0, st[v], -1); upd(0, ft[v]+1, +1); upd(0, st[f[par[0][v]]], +1); upd(0, ft[f[par[0][v]]]+1, -1); f[par[0][v]] = v; } u = par[0][v]; } } } int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...