C++14(g++5.4) 解法, 执行用时: 358ms, 内存消耗: 24380K, 提交时间: 2020-10-04 19:15:50

#include<bits/stdc++.h>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define sz(a) int(a.size())
#define rson mid+1,r,p<<1|1
#define pii pair<int,int>
#define lson l,mid,p<<1
#define ll long long
#define pb push_back
#define mp make_pair
#define se second
#define fi first
using namespace std;
const double eps=1e-8;
const int mod=1e9+7;
const int N=1e5+10;
const int inf=1e9;
int n,m;
vector<int>g[N];
int c[N],d[N],f[N],p[N],sz[N],top[N],son[N],ans[N],tot;
struct cmp{
	bool operator() (const int &x,const int &y)const{
		return p[x]<p[y];
	}
};
set<int,cmp>st[N];
void dfs(int u){
	d[u]=d[f[u]]+1;
	sz[u]=1;
	for(int x:g[u]){
		if(x==f[u]) continue;
		f[x]=u;
		dfs(x);
		sz[u]+=sz[x];
		if(sz[son[u]]<sz[x]) son[u]=x;
	}
}
void dfs1(int u,int t){
	p[u]=++tot;top[u]=t;
	if(son[u]) dfs1(son[u],t);
	for(int x:g[u]){
		if(x==f[u]||x==son[u]) continue;
		dfs1(x,x);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]]) swap(x,y);
		x=f[top[x]];
	}
	if(d[x]<d[y]) swap(x,y);
	return y;
}
int dis(int x,int y){
	return d[x]+d[y]-2*d[lca(x,y)];
}
void add(int x){
	st[c[x]].insert(x);
	auto it=st[c[x]].find(x);
	int l=0,r=0;
	++it;
	if(it!=st[c[x]].end()){
		r=*it;
	}
	--it;
	if(it!=st[c[x]].begin()){
		--it;
		l=*it;
	}
	if(l&&r) ans[c[x]]-=dis(l,r);
	if(l) ans[c[x]]+=dis(l,x);
	if(r) ans[c[x]]+=dis(r,x);
}
void del(int x){
	auto it=st[c[x]].find(x);
	int l=0,r=0;
	++it;
	if(it!=st[c[x]].end()){
		r=*it;
	}
	--it;
	if(it!=st[c[x]].begin()){
		--it;
		l=*it;
	}
	if(l&&r) ans[c[x]]+=dis(l,r);
	if(l) ans[c[x]]-=dis(l,x);
	if(r) ans[c[x]]-=dis(r,x);	
	st[c[x]].erase(x);
}
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n;
	rep(i,2,n){
		int x,y;
		cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dfs(1);dfs1(1,1);
	rep(i,1,n){
		cin>>c[i];
		add(i);
	}
	cin>>m;
	while(m--){
		char cs;
		cin>>cs;
		int x,y;
		if(cs=='U'){
			cin>>x>>y;
			del(x);
			c[x]=y;
			add(x);
		}else{
			cin>>y;
			if(st[y].empty()) cout<<"-1\n";
			else cout<<(ans[y]+dis(*st[y].begin(),*st[y].rbegin()))/2<<'\n';
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 550ms, 内存消耗: 28792K, 提交时间: 2020-10-04 12:17:40

// In the name of God.
// Ya Ali!

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 17, lg = 17;
int n, h[maxn], col[maxn], par[lg][maxn], st[maxn], c[maxn];
vector<int> g[maxn];
void dfs(int v = 0, int p = -1){
	static int t = 0;
	st[v] = t++;
	for(auto u : g[v])
		if(u != p){
			par[0][u] = v;
			h[u] = h[v] + 1;
			dfs(u, v);
		}
}
int dis(int v, int u){
	if(h[u] < h[v])
		swap(v, u);
	int ans = 0;
	for(int i = 0; i < lg; i++)
		if(h[u] - h[v] >> i & 1){
			u = par[i][u];
			ans += 1 << i;
		}
	for(int i = lg - 1; i >= 0; i--)
		if(par[i][v] != par[i][u]){
			ans += 1 << i + 1;
			v = par[i][v];
			u = par[i][u];
		}	
	return v == u ? ans : ans + 2;
}
struct Stcmp{
	  bool operator() (const int& lhs, const int& rhs) const{
		  return st[lhs] < st[rhs];
	  }
};
struct S{
	set<int, Stcmp> s;
	int ans;
	void insert(int v, int z){
		if(s.size()){	
			int prv, nxt;
			{
				auto it = s.lower_bound(v);
				if(it == s.begin())
					prv = *s.rbegin();
				else
					prv = *--it;
			}
			{
				auto it = s.upper_bound(v);
				if(it == s.end())
					nxt = *s.begin();
				else
					nxt = *it;
			}
			ans += z * (dis(prv, v) + dis(v, nxt) - dis(prv, nxt)) / 2;
		}
		if(z == 1)
			s.insert(v);
		else
			s.erase(v);
	}
}  s[maxn];
int main(){
	ios::sync_with_stdio(0), cin.tie();
	cin >> n;
	for(int i = 1; i < n; i++){
		int v, u;
		cin >> v >> u;
		v--, u--;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	dfs();
	for(int k = 1; k < lg; k++)
		for(int v = 0; v < n; v++)
			par[k][v] = par[k - 1][ par[k - 1][v] ];
	for(int i = 0; i < n; i++){
		cin >> c[i];
		s[ c[i] ].insert(i, +1);
	}
	int m;
	cin >> m;
	while(m--){
		char t;
		cin >> t;
		if(t == 'U'){
			int v, newc;
			cin >> v >> newc;
			v--;
			s[ c[v] ].insert(v, -1);
			s[ c[v] = newc ].insert(v, +1);
		}
		else{
			int c;
			cin >> c;
			cout << (s[c].s.size() == 0 ? -1 : s[c].ans) << '\n';
		}
	}
}