제출 #518999

#제출 시각아이디문제언어결과실행 시간메모리
518999KeshiUnique Cities (JOI19_ho_t5)C++17
100 / 100
1056 ms73652 KiB
//In the name of God #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int maxn = 2e5 + 100; const int mod = 1e9 + 7; const int inf = 1e9; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() #define lc (id << 1) #define rc (lc | 1) ll pw(ll a, ll b){ ll c = 1; while(b){ if(b & 1) c = c * a % mod; a = a * a % mod; b >>= 1; } return c; } int n, m, c[maxn], d[maxn], mx, r1, r2, dd[maxn], ans[maxn], prv[maxn]; vector<int> g[maxn]; bool vis[maxn]; int seg[maxn << 2], lz[maxn << 2], cnt[maxn << 2]; void bld(int id, int s, int e){ seg[id] = lz[id] = 0; cnt[id] = e - s; if(e - s == 1) return; int mid = (s + e) >> 1; bld(lc, s, mid); bld(rc, mid, e); return; } void upd(int id, int s, int e, int l, int r, int x){ if(r <= s || e <= l) return; if(l <= s && e <= r){ seg[id] += x; lz[id] += x; return; } int mid = (s + e) >> 1; seg[lc] += lz[id]; lz[lc] += lz[id]; seg[rc] += lz[id]; lz[rc] += lz[id]; lz[id] = 0; upd(lc, s, mid, l, r, x); upd(rc, mid, e, l, r, x); seg[id] = min(seg[lc], seg[rc]); cnt[id] = 0; if(seg[id] == seg[lc]) cnt[id] += cnt[lc]; if(seg[id] == seg[rc]) cnt[id] += cnt[rc]; return; } int get(int id, int s, int e, int l, int r){ if(r <= s || e <= l) return inf; if(l <= s && e <= r) return seg[id]; int mid = (s + e) >> 1; seg[lc] += lz[id]; lz[lc] += lz[id]; seg[rc] += lz[id]; lz[rc] += lz[id]; lz[id] = 0; return min(get(lc, s, mid, l, r), get(rc, mid, e, l, r)); } void difs(int v){ vis[v] = 1; if(d[v] > d[mx]) mx = v; for(int u : g[v]){ if(vis[u]) continue; d[u] = d[v] + 1; difs(u); } return; } vector<int> gg[maxn]; void prep(int v, int p = -1){ gg[v].clear(); dd[v] = d[v]; for(int u : g[v]){ if(u == p) continue; d[u] = d[v] + 1; gg[v].pb(u); prep(u, v); dd[v] = max(dd[v], dd[u]); } return; } void solve(int v){ upd(1, 0, n, d[v] - (dd[v] - d[v]), d[v], 1); ans[v] = max(ans[v], cnt[1] - (n - d[v])); upd(1, 0, n, d[v] - (dd[v] - d[v]), d[v], -1); vector<pll> vec; vec.pb(Mp(-d[v], v)); for(int u : gg[v]){ vec.pb(Mp(-dd[u], u)); } sort(all(vec)); for(int u : gg[v]){ int x = d[v] - (-vec[0].F - d[v]); if(u == vec[0].S){ x = d[v] - (-vec[1].F - d[v]); } upd(1, 0, n, x, d[v], 1); int pr = prv[c[v]]; if(pr == 0 || get(1, 0, n, d[pr], d[pr] + 1) != 0){ prv[c[v]] = v; } else{ upd(1, 0, n, d[v], d[v] + 1, 1); } solve(u); if(prv[c[v]] == v){ prv[c[v]] = pr; } else{ upd(1, 0, n, d[v], d[v] + 1, -1); } upd(1, 0, n, x, d[v], -1); } return; } int main(){ fast_io; cin >> n >> m; for(int i = 1; i < n; i++){ int v, u; cin >> v >> u; g[v].pb(u); g[u].pb(v); } for(int i = 1; i <= n; i++){ cin >> c[i]; } d[1] = 0; difs(1); r1 = mx; fill(vis, vis + n + 10, 0); d[r1] = 0; difs(r1); r2 = mx; d[r1] = 0; prep(r1); bld(1, 0, n); solve(r1); d[r2] = 0; prep(r2); bld(1, 0, n); solve(r2); for(int i = 1; i <= n; i++){ cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...