编程之美2015初赛第一场 hihoCoder #1156 : 彩色的树（染色问题）-白红宇

编程之美2015初赛第一场 hihoCoder #1156 : 彩色的树（染色问题）

阅读量：6755 次

发布时间：2019-06-26

本文共 1357 字，大约阅读时间需要 4 分钟。

#1156 : 彩色的树

时间限制:2000ms单点时限:1000ms内存限制:256MB

描述

给定一棵n个节点的树，节点编号为1, 2, …, n。树中有n - 1条边，任意两个节点间恰好有一条路径。这是一棵彩色的树，每个节点恰好可以染一种颜色。初始时，所有节点的颜色都为0。现在需要实现两种操作:1. 改变节点x的颜色为y；2. 询问整棵树被划分成了多少棵颜色相同的子树。即每棵子树内的节点颜色都相同，而相邻子树的颜色不同。

输入

第一行一个整数T，表示数据组数，以下是T组数据。每组数据第一行是n，表示树的节点个数。接下来n - 1行每行两个数i和j，表示节点i和j间有一条边。接下来是一个数q，表示操作数。之后q行，每行表示以下两种操作之一：1. 若为"1"，则询问划分的子树个数。2. 若为"2 x y"，则将节点x的颜色改为y。

输出

每组数据的第一行为"Case #X:"，X为测试数据编号，从1开始。接下来的每一行，对于每一个询问，输出一个整数，为划分成的子树个数。

数据范围

1 ≤ T ≤ 200 ≤ y ≤ 100000

小数据

1 ≤ n, q ≤ 5000

大数据

1 ≤ n, q ≤ 100000

样例输入

231 22 3312 2 1151 22 32 42 5412 2 12 3 21

样例输出

Case #1:13Case #2:15

解题步骤：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

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
             6 #include
             
               7 #include
              
                8 using namespace std; 9 #define N 10000610 int n;11 vector
               
                 edge[N];//保存边12 int fa[N];//记录父节点13 map
                
                 mp[N];//mp[i][j]=k表示第i个结点的颜色是j，并且和它同颜色的儿子结点数为k14 int color[N];//color用来记录结点的颜色,初始化为015 void bfs()16 {17 queue
                 
                   q;18 q.push(1);19 fa[1]=0;20 while(!q.empty())21 {22 int u=q.front();23 q.pop();24 for(int i=0;i