Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
DSU on tree (http://codeforces.com/contest/600/problem/E)
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
#include <bits/stdc++.h> using namespace std; #define pb push_back typedef long long int ll; const int N = 1e5 + 1; vector<int> g[N]; ll big[N] = {0}, sub[N], col[N], cnt[N] = {0}, sum[N] = {0}, ans[N] = {0}; void dfs(int s, int p){ sub[s] = 1; for(auto &i : g[s]) if(i != p){ dfs(i, s), sub[s] += sub[i]; if(sub[i] > sub[g[s][0]]) swap(i, g[s][0]); } } multiset<int> st; void add(int s, int p, int v){ int cur = col[s]; if(cnt[cur] != 0) st.erase(st.find(cnt[cur])), sum[cnt[cur]] -= cur; cnt[cur] += v; if(cnt[cur] != 0) st.insert(cnt[cur]), sum[cnt[cur]] += cur; for(auto i : g[s]) if(i != p && !big[i]) add(i, s, v); } void dfs_dsu(int s, int p, bool keep){ int x = g[s][0]; for(auto i : g[s]) if(i != x && i != p) dfs_dsu(i, s, 0); if(x != p) dfs_dsu(x, s, 1), big[x] = 1; add(s, p, 1); ans[s] = sum[*st.rbegin()]; if(x != p) big[x] = 0; if(!keep) add(s, p, -1); } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int j = 1; j <= n; j++) cin >> col[j]; for(int j = 0; j < n-1; j++){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); } dfs(1, 0); dfs_dsu(1, 0, 0); for(int j = 1; j <= n; j++) cout << ans[j] << " "; cout << endl; return 0; }
g++
15 1 2 3 1 2 3 3 1 1 3 2 2 1 2 3 1 2 1 3 1 4 1 14 1 15 2 5 2 6 2 7 3 8 3 9 3 10 4 11 4 12 4 13
Show compiler warnings
[
+
] Compiler args
[
-
]
Show input
Compilation time: 1.63 sec, absolute running time: 0.09 sec, cpu time: 0.03 sec, memory peak: 3 Mb, absolute service time: 1,73 sec
edit mode
|
history
|
discussion
6 5 4 3 2 3 3 1 1 3 2 2 1 2 3