#1156 : 彩色的树
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
给定一棵n个节点的树，节点编号为1, , …, n。树中有n - 1条边，任意两个节点间恰好有一条路径。这是一棵彩色的树，每个节点恰好可以染一种颜色。初始时，所有节点的颜色都为0。现在需要实现两种操作: . 改变节点x的颜色为y； . 询问整棵树被划分成了多少棵颜色相同的子树。即每棵子树内的节点颜色都相同，而相邻子树的颜色不同。
输入
第一行一个整数T，表示数据组数，以下是T组数据。 每组数据第一行是n，表示树的节点个数。接下来n - 1行每行两个数i和j，表示节点i和j间有一条边。接下来是一个数q，表示操作数。之后q行，每行表示以下两种操作之一： . 若为""，则询问划分的子树个数。 . 若为"2 x y"，则将节点x的颜色改为y。
输出
每组数据的第一行为"Case #X:"，X为测试数据编号，从1开始。 接下来的每一行，对于每一个询问，输出一个整数，为划分成的子树个数。
数据范围
≤ T ≤ ≤ y ≤
小数据
≤ n, q ≤
大数据
≤ n, q ≤
- 样例输入
- 样例输出
Case #: Case #:
解题步骤：1、求出所有点的父结点，这边用的bfs遍历
2、使用一个map<int,int>mp[N],mp[i][j]=k表示第i个结点的颜色是j，并且和它同颜色的儿子结点数为k
3、ans开始只有1
4、color数组初始化为0
5、如果要更新颜色，求出变化的子树数量，更新ans
6、至于子树数量的变化，如x的颜色变为y，那么先求出x颜色没变化时的子结点ans0，再求出颜色变化后的子结点ans1，然后ans=ans+ans0-ans1,更新ans
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
#define N 100006
int n;
vector<int> edge[N];//保存边
int fa[N];//记录父节点
map<int,int>mp[N];//mp[i][j]=k表示第i个结点的颜色是j，并且和它同颜色的儿子结点数为k
int color[N];//color用来记录结点的颜色,初始化为0
void bfs()
{
queue<int> q;
q.push();
fa[]=;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=;i<edge[u].size();i++)
{
int v=edge[u][i];
if(fa[v]!=-) continue;
fa[v]=u;
q.push(v);
}
}
}
int main()
{
int t;
scanf("%d",&t);
int ac=;
while(t--)
{
printf("Case #%d:\n",++ac);
for(int i=;i<N;i++)edge[i].clear();
memset(fa,-,sizeof(fa)); scanf("%d",&n);
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
} bfs();//bfs用来求所有的点的父节点，待会要用到 for(int i=;i<=n;i++)
{
mp[i].clear();
color[i]=;
if(i==) mp[i][]=edge[i].size();
else mp[i][]=edge[i].size()-;//这边减掉1的原因是i肯定要和1这个根结点相连，所以减1
}
//for(int i=1;i<=n;i++)
//printf("--%d\n",mp[i][0]); int q;
scanf("%d",&q);
int ans=;
while(q--)
{
int c;
scanf("%d",&c);
if(c==) printf("%d\n",ans);//如果是1就输出结果,开始只有一棵
else
{
int x,y;
scanf("%d%d",&x,&y);
int ans0=mp[x][color[x]];//ans0表示还未变色时x的子结点总数
if(x!= && color[fa[x]]==color[x]) ans0++;//如果不是根结点，并且x的父结点和它颜色相同，则++ int ans1=mp[x][y];//ans1表示x变完颜色后的子结点个数
if(x!= && color[fa[x]]==y) ans1++;//如果不是根结点，并且x的父结点和它颜色相同，则++ ans=ans+ans0-ans1;//ans加上增加的子树 if(x!=)
{
mp[fa[x]][color[x]]--;//因为要变色，所以父结点的子结点 -1
color[x]=y;//将颜色改变
mp[fa[x]][color[x]]++;//当前颜色的子结点 +1
}
color[x]=y;//如果是根节点的话，
}
}
}
return ;
}