C++14(g++5.4) 解法, 执行用时: 504ms, 内存消耗: 63948K, 提交时间: 2019-04-29 15:48:03

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1 << 17;
vector<int> G[maxn], sp;
int dep[maxn], dfn[maxn];
pair<int, int> dp[20][maxn << 1];

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    dfn[u] = sp.size();
    sp.push_back(u);
    for (auto& v : G[u])
    {
        if (v == fa) continue;
        dfs(v, u);
        sp.push_back(u);
    }
}

void initrmq()
{
    int n = sp.size();
    for (int i = 0; i < n; i++) dp[0][i] = {dfn[sp[i]], sp[i]};
    for (int i = 1; (1 << i) <= n; i++)
        for (int j = 0; j + (1 << i) - 1 < n; j++)
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
}
int lca(int u, int v)
{
    // int l = dfn[u], r = dfn[v];
    int l = u, r = v;
    if (l > r) swap(l, r);
    int k = __lg(r - l + 1);
    return min(dp[k][l], dp[k][r - (1 << k) + 1]).second;
}

int col[maxn];
int ans[maxn];
set<int> s[maxn];

void gao(int x, int d)
{
    int c = col[x];
    ans[c] += d * dep[x];
    if (d == 1) s[c].insert(dfn[x]);
    auto it = s[c].find(dfn[x]);
    auto pre = it, suf = it;
    ++suf;
    if (it != s[c].begin()) --pre, ans[c] -= d * dep[lca(*pre, *it)];
    if (suf != s[c].end())
    {
        ans[c] -= d * dep[lca(*it, *suf)];
        if (it != s[c].begin()) ans[c] += d * dep[lca(*pre, *suf)];
    }
    if (d == -1) s[c].erase(dfn[x]);
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    initrmq();
    for (int i = 1; i <= n; i++) scanf("%d", &col[i]), gao(i, 1);
    for (int i = 0, op, x; i < m; i++)
    {
        scanf("%d%d", &op, &x);
        if (op == 1)
        {
            gao(x, -1);
            scanf("%d", &col[x]);
            gao(x, 1);
        }
        else
        {
            if (s[x].empty())
                puts("0");
            else
                printf("%d\n", ans[x] - dep[lca(*s[x].begin(), *s[x].rbegin())] + 1);
        }
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 444ms, 内存消耗: 18516K, 提交时间: 2019-04-20 14:25:59

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=1e5+5;
int n,m,col[N],fa[N],dep[N],sz[N],top[N],dfn[N],tim,id[N],ans[N];
vector<int>E[N];set<int>S[N];set<int>::iterator it,pre,suf;
void dfs1(int u,int f){
	fa[u]=f;dep[u]=dep[f]+1;sz[u]=1;
	for(int v:E[u])if(v!=f)dfs1(v,u),sz[u]+=sz[v];
}
void dfs2(int u,int f){
	top[u]=f;id[dfn[u]=++tim]=u;int son=0;
	for(int v:E[u])if(v!=fa[u]&&sz[v]>sz[son])son=v;
	if(son)dfs2(son,f);
	for(int v:E[u])if(v!=fa[u]&&v!=son)dfs2(v,v);
}
int lca(int u,int v){
	u=id[u],v=id[v];
	while(top[u]^top[v])
		if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
		else v=fa[top[v]];
	return dep[u]<dep[v]?u:v;
}
void insert(int x){
	int c=col[x];ans[c]+=dep[x];
	S[c].insert(dfn[x]);it=S[c].find(dfn[x]);
	if(it!=S[c].begin())pre=it,--pre,ans[c]-=dep[lca(*pre,*it)];
	suf=it;++suf;if(suf!=S[c].end()){
		ans[c]-=dep[lca(*it,*suf)];
		if(it!=S[c].begin())ans[c]+=dep[lca(*pre,*suf)];
	}
}
void erase(int x){
	int c=col[x];ans[c]-=dep[x];
	it=S[c].find(dfn[x]);
	if(it!=S[c].begin())pre=it,--pre,ans[c]+=dep[lca(*pre,*it)];
	suf=it;++suf;if(suf!=S[c].end()){
		ans[c]+=dep[lca(*it,*suf)];
		if(it!=S[c].begin())ans[c]-=dep[lca(*pre,*suf)];
	}
	S[c].erase(dfn[x]);
}
int main(){
	n=gi();m=gi();
	for(int i=1;i<n;++i){
		int u=gi(),v=gi();
		E[u].push_back(v);E[v].push_back(u);
	}
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=n;++i)col[i]=gi(),insert(i);
	while(m--){
		int op=gi(),x=gi();
		if(op==1)erase(x),col[x]=gi(),insert(x);
		else{
			if(!S[x].size())puts("0");
			else printf("%d\n",ans[x]-dep[lca(*S[x].begin(),*S[x].rbegin())]+1);
		}
	}
	return 0;
}