제출 #773553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773553		1bin	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	2076 ms	14852 KiB

joi2019_ho_t5

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int n, m, C[NMAX], D[NMAX], a, b, mxd, ix, r1, r2, ans[NMAX], cur, cnt[NMAX], mx[NMAX][2], idx[NMAX][2];
vector<int> adj[NMAX];

void dfs2(int x, int p, int d){
    if(d > mxd) mxd = d, ix = x;
    for(int&nx : adj[x])
        if(nx != p) dfs2(nx, x, d + 1);
    return;
}

void go(int x, int p){
    mx[x][0] = mx[x][1] = 0;
    for(int& nx : adj[x])
        if(nx != p){
            go(nx, x);
            if(mx[nx][0] + 1 > mx[x][1]) mx[x][1] = mx[nx][0] + 1, idx[x][1] = nx;
            if(mx[x][0] < mx[x][1]){
                swap(mx[x][0], mx[x][1]);
                swap(idx[x][0], idx[x][1]);
            }
        }
    return;
}

void f(int x, int add){
    if(add){
        if(++cnt[C[x]] == 1) cur++;
    }
    else{
        if(--cnt[C[x]] == 0) cur--;
    }
    return;
}

stack<int> st;
void dfs(int x, int p, int d){
    stack<int> t;
    D[d] = x;
    
    auto calc = [&] (int mxd){
        while(st.size() && st.top() >= mxd){
            f(D[st.top()], 0);
            t.emplace(st.top()); st.pop();
        }
    };
    if(mx[x][0]){
        int nx = idx[x][0];
        if(mx[x][1]) calc(d - mx[x][1]);
        st.emplace(d); f(x, 1);
        dfs(nx, x, d + 1);
        st.pop(); f(x, 0);
        
        calc(d - mx[x][0]);
        for(int& nx : adj[x])
            if(nx != p && nx != mx[x][0]){
                st.emplace(d); f(x, 1);
                dfs(nx, x, d + 1);
                st.pop(); f(x, 0);
            }
    }
    ans[x] = max(ans[x], cur);
    while(t.size()){
        f(D[t.top()], 1);
        st.emplace(t.top()); t.pop();
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }    
    for(int i = 1; i <= n; i++) cin >> C[i];
    dfs2(1, -1, 0);
    r1 = ix;
    mxd = 0; dfs2(r1, -1, 0);
    r2 = ix;
    
    go(r1, -1); dfs(r1, -1, 0);
    go(r2, -1); dfs(r2, -1, 0);
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}

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