제출 #1217293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217293		JooDdae	Unique Cities (JOI19_ho_t5)	C++20	100 / 100	179 ms	39272 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, c[200200], d[200200], ans[200200], h[200200];
vector<int> v[200200];

int dfs(int u, int p) {
    h[u] = 1, d[u] = d[p]+1;
    for(auto x : v[u]) if(x != p) h[u] = max(h[u], dfs(x, u)+1);
    return h[u];
}

vector<int> st;
int cnt, C[200200];

void pop() {
    if(!--C[c[st.back()]]) cnt--;
    st.pop_back();
}

void add(int u) {
    if(!C[c[u]]++) cnt++;
    st.push_back(u);
}

void dfs2(int u, int p) {
    if(p && v[u].size() == 1) {
        ans[u] = max(ans[u], cnt);
        return;
    }

    int C = !!p;
    sort(v[u].begin(), v[u].end(), [&](int a, int b){ return h[a] > h[b]; });
    while(v[u].size() > 2 && !st.empty() && d[u]-d[st.back()] <= h[v[u][2]]) pop();
    add(u);
    dfs2(v[u][C], u);

    while(!st.empty() && d[u]-d[st.back()] <= h[v[u][C]]) pop();
    ans[u] = max(ans[u], cnt);

    for(int i=C+1;i<v[u].size();i++) {
        while(!st.empty() && d[st.back()] >= d[u]) pop();
        add(u);
        dfs2(v[u][i], u);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<n;i++) {
        int x, y; cin >> x >> y;
        v[x].push_back(y), v[y].push_back(x);
    }
    for(int i=1;i<=n;i++) cin >> c[i];

    dfs(1, 0);
    int L = max_element(d+1, d+1+n) - d;
    dfs(L, 0);
    int R = max_element(d+1, d+1+n) - d;

    for(auto r : {L, R}) {
        while(!st.empty()) pop();
        dfs(r, 0), dfs2(r, 0);
    }

    for(int i=1;i<=n;i++) cout << ans[i] << "\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32