独特的城市[JOI 2019 Final]

发表于 分类于

题目链接

loj

题解

似乎跟树的直径有点关系。不管了，先画出一条直径。

先考虑比较简单的，假设我们不考虑颜色的限制，只需维护有几个点满足条件。

可以发现，对于一个点 $i$，对该点有所贡献的所有点都会出现在 $i$ 到直径某个端点中的路径中。那么就可以尝试对于这两个端点dfs，那么满足条件的点必然在他到根的路径中。然后拿一个什么东西去维护这些点。

假设当前dfs到点 $u$，准备去dfs点 $v$。那么对于这个 $v$ 而言，$u$ 是有可能有贡献的，把它加到那个集合里。但是这时 $v$ 的兄弟会对 $v$ 的答案产生限制。记 $v$ 的所有兄弟离他们的子树中叶子结点的最大值为 $mx$，那么答案集合中的距离 $v$ 小于等于 $mx$ 的点都变得不合法，并且都 $v$ 的子树的所有点也会不合法。那么就可以把这些点从这个集合删去。

对于一个点统计答案的时候，记 $u$ 的所有儿子离其子树中叶节点的距离最大值为 $x$，那么答案集合中的距离 $u$ 小于等于 $x$ 的点都变得不合法，也同样删去。

这个集合可以用栈来维护。

离子树叶节点的距离最大值用长链剖分即可。

最后来考虑颜色的限制，也就是满足条件的集合中有多少种不同的颜色。

用个桶维护一下不就好了嘛。。。

时间复杂度 $O(n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=200010;
int ver[N<<1],ne[N<<1],head[N],tot=1;
inline void add(int x,int y)
{
	ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
	ver[++tot]=x; ne[tot]=head[y]; head[y]=tot;
}
int n,m,s,t,ans[N];
int d[N];
queue<int> q;
void bfs(int u,int &s)
{
	fo(i,1,n) d[i]=0;
	d[u]=1; q.push(u);
	for(int u;!q.empty();)
	{
		u=q.front(); q.pop();
		for(int i=head[u],v;i;i=ne[i])
		{
			v=ver[i];
			if(!d[v]) {d[v]=d[u]+1; q.push(v);}
		}
	}
	s=u;
	fo(i,1,n) if(d[i]>d[s]) s=i;
}
void find()
{
	bfs(1,s);
	bfs(s,t);
}
int dep[N],len[N],son[N];
void dfs(int u,int pre)
{
	len[u]=1; dep[u]=dep[pre]+1; son[u]=0;
	for(int i=head[u],v;i;i=ne[i])
		if((v=ver[i])!=pre)
		{
			dfs(v,u);
			len[u]=max(len[u],len[v]+1);
			if(!son[u]||len[son[u]]<len[v]) son[u]=v;
		}
}
int st[N],top;
int w[N],col[N],now;
inline void add(int x)
{
	st[++top]=x;
	w[col[x]]++;
	if(w[col[x]]==1) now++;
}
inline void del()
{
	if(w[col[st[top]]]==1) now--;
	w[col[st[top]]]--;
	top--;
}
void solve(int u,int pre)
{
	if(!son[u]) {ans[u]=max(ans[u],now); add(u); return;}
	int mx=0;
	for(int i=head[u],v;i;i=ne[i])
	{
		v=ver[i];
		if(v==son[u]||v==pre) continue;
		mx=max(mx,len[v]);
	}
	for(;top&&dep[u]-dep[st[top]]<=mx;) del();
	add(u);
	solve(son[u],u);
	for(int i=head[u],v;i;i=ne[i])
	{
		v=ver[i];
		if(v==son[u]||v==pre) continue;
		for(;top&&dep[u]-dep[st[top]]<=len[son[u]];) del();
		add(u);
		solve(v,u);
	}
	for(;top&&dep[u]-dep[st[top]]<=len[son[u]];) del();
	ans[u]=max(ans[u],now);
}
void work()
{
	swap(s,t);
	top=now=0; dfs(s,0); solve(s,0);
	fo(i,0,m) w[i]=0;
	top=now=0; dfs(t,0); solve(t,0);
	fo(i,1,n) printf("%d\n",ans[i]);
}
int main()
{
	n=read(); m=read();
	fo(i,2,n) add(read(),read());
	find();
	fo(i,1,n) col[i]=read();
	work();
	return 0;
}