点分治/贪心
对于点分治的理解不够深刻...点分治能统计树上每个点对的信息，那么这里就是统计同种颜色点对之间的最大距离，自然可以用点分
然后点分，每次统计最大距离，但是略微卡常...
还有一种贪心的方法，每种颜色必然选以某点为根最深的节点，计算出最深的节点，然后dfs，看每种颜色，然后和最深的节点计算距离
#include<bits/stdc++.h> using namespace std; const int N = 200010; int n, top, root, k, top1; vector<int> G[N]; int size[N], mx[N], mark[N], ans[N], st[N], st1[N], c[N], a[N], mx_deep[N], now_deep[N], vis[N], vis1[N]; namespace IO { const int Maxlen = N * 50; char buf[Maxlen], *C = buf; int Len; inline void read_in() { Len = fread(C, 1, Maxlen, stdin); buf[Len] = ' '; } inline void fread(int &x) { x = 0; int f = 1; while (*C < '0' || '9' < *C) { if(*C == '-') f = -1; ++C; } while ('0' <= *C && *C <= '9') x = (x << 1) + (x << 3) + *C - '0', ++C; x *= f; } inline void read(int &x) { x = 0; int f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); } x *= f; } inline void read(long long &x) { x = 0; long long f = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = (x << 1ll) + (x << 3ll) + c - '0'; c = getchar(); } x *= f; } } using namespace IO; void findroot(int u, int last, int tot) { size[u] = 1; mx[u] = 0; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == last || mark[v]) continue; findroot(v, u, tot); size[u] += size[v]; if(size[v] > mx[u]) mx[u] = size[v]; } mx[u] = max(mx[u], tot - mx[u]); if(mx[u] < mx[root]) root = u; } void dfs(int u, int last, int deep) { if(mx_deep[a[u]] == -1) st[++top] = a[u]; mx_deep[a[u]] = max(mx_deep[a[u]], deep); for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == last || mark[v]) continue; dfs(v, u, deep + 1); } } int get_size(int u, int last) { int ret = 1; for(int i = 0; i < G[u].size(); ++i) { int v = G[u][i]; if(v == last || mark[v]) continue; ret += get_size(v, u); } return ret; } void divide(int u) { root = 0; findroot(u, 0, get_size(u, 0)); mark[root] = 1; now_deep[a[root]] = 0; st1[++top1] = a[root]; for(int i = 0; i < G[root].size(); ++i) { int v = G[root][i]; if(mark[v]) continue; dfs(v, root, 1); if(mx_deep[a[root]] == -1) st[++top] = a[root], mx_deep[a[root]] = 0; for(int j = top; j; --j) if(now_deep[st[j]] != -1) ans[st[j]] = max(ans[st[j]], now_deep[st[j]] + mx_deep[st[j]]); while(top) { if(now_deep[st[top]] == -1) st1[++top1] = st[top]; now_deep[st[top]] = max(now_deep[st[top]], mx_deep[st[top]]); mx_deep[st[top--]] = -1; } } while(top1) now_deep[st1[top1--]] = -1; for(int i = 0, now = root; i < G[now].size(); ++i) { int v = G[now][i]; if(mark[v]) continue; divide(v); } } int main() { memset(now_deep, -1, sizeof(now_deep)); memset(mx_deep, -1, sizeof(mx_deep)); read_in(); fread(n); fread(k); for(int i = 1; i <= n; ++i) { int u; fread(a[i]); fread(u); if(u) { G[u].push_back(i); G[i].push_back(u); } } mx[0] = 1 << 29; divide(1); for(int i = 1; i <= k; ++i) printf("%d ", ans[i]); return 0; }