TLE on #16

最后一个点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll x = 0,h = 1;
	char ch = getchar();
	while(!(ch=='-'||('0'<=ch&&ch<='9'))) ch = getchar();
	if(ch=='-') h = -1;
	else x = ch-'0';
	ch = getchar();
	while('0'<=ch&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*h;
}
const ll N = 100010;
ll n,a[N];
vector<ll> vec[N];
map<ll,ll> P;
map<ll,ll> rp;
ll tot = 0;
map<ll,ll> totl;
ll dep[N];
struct quest{
	ll x,y;
} Q[N];
ll qtot = 0;
ll bs[N][N/1000];
void dfs(ll id,ll fa,ll depth){
	dep[id] = depth;
	if(a[id]) bs[id][a[id]] = 1;
	for(auto v : vec[id]){
		if(v==fa) continue;
		dfs(v,id,depth+1);
		for(ll j = 1; j <= tot; j++) bs[id][j]+=bs[v][j];
	}
}

int main(){
	n = read();
	for(ll i = 1; i < n; i++){
		ll u = read(),v = read();
		vec[u].push_back(v);
		vec[v].push_back(u);
		qtot++;
		Q[qtot].x = u;
		Q[qtot].y = v;
	}
	for(ll i = 1; i <= n; i++) a[i] = read();
	for(ll i = 1; i <= n; i++){
		totl[a[i]]++;
	}
	for(ll i = 1; i <= n; i++){
		if(totl[a[i]]==2){
			if(P[a[i]]){
				a[i] = P[a[i]];
				continue;
			}
			tot++;
			P[a[i]] = tot;
			rp[tot] = a[i];
			a[i] = P[a[i]];
		} else a[i] = 0;
	}
	 dfs(1,1,1);
	for(ll i = 1; i <= qtot; i++){
		ll u = Q[i].x,v = Q[i].y;
		if(dep[u]>dep[v]) swap(u,v);
		ll res = 0;
		for(ll j = 1; j <= tot; j++){
			if(bs[v][j]!=1){
				res = max(res,rp[j]);
			}
		}
		printf("%lld\n",res);
	}
	return 0;
}