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 ≤ 20
0 ≤ y ≤ 100000
小数据
1 ≤ n, q ≤ 5000
大数据
1 ≤ n, q ≤ 100000
- 样例输入
-
2 3 1 2 2 3 3 1 2 2 1 1 5 1 2 2 3 2 4 2 5 4 1 2 2 1 2 3 2 1
- 样例输出
-
Case #1: 1 3 Case #2: 1 5
由于无环，和断点（改变颜色的点）连接的点如果颜色和改变前一样，树++。和改变后一样树--。
代码一号，树上乱搞：
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int maxn=220010; int Laxt[maxn],Next[maxn],To[maxn],cnt; int ans,V[maxn];void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; } void init() { ans=1;cnt=0; memset(Laxt,0,sizeof(Laxt)); memset(V,0,sizeof(V)); } void change(int x,int y) { bool flag=false; int tmp=0; for(int i=Laxt[x];i;i=Next[i]){ if(V[To[i]]==y) ans--; if(V[To[i]]==V[x]) ans++; } V[x]=y; } int main() { int T,n,i,j,x,y,q,u,v,Case=0; scanf("%d",&T); while(T--){ printf("Case #%d: ",++Case); init(); scanf("%d",&n); for(i=1;i<n;i++){ scanf("%d%d",&u,&v); add(u,v); add(v,u); } scanf("%d",&q); while(q--){ scanf("%d",&x); if(x==1) printf("%d ",ans); else { scanf("%d%d",&x,&y); change(x,y); } } } return 0; }
每次访问邻边导致耗时过多。怎么记录？
首先，无向图变有向图，==其实就是父子关系辣。
一个节点记录相邻儿子的信息。如果改变某点，就只改变它父亲的信息就ok。
强势之处：
通过父子关系使记录和查询变成O(1)，访问效率高；
map记录每个节点的有效颜色，空间利用效率高。
代码二号：
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<map> using namespace std; const int maxn=110010; int Laxt[maxn],Next[maxn<<1],To[maxn<<1],cnt; int ans,V[maxn],fa[maxn]; map<int,int>G[maxn]; void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; } void init() { ans=1;cnt=0; memset(Laxt,0,sizeof(Laxt)); memset(V,0,sizeof(V)); } void change(int x,int y) { if(V[x]==y) return ; ans+=G[x][V[x]]; ans-=G[x][y]; if(fa[x]!=0){ if(V[fa[x]]==V[x]) ans++; if(V[fa[x]]==y) ans--; G[fa[x]][V[x]]--; G[fa[x]][y]++; } V[x]=y; } void dfs(int u,int pre) { fa[u]=pre; for(int i=Laxt[u];i;i=Next[i]){ if(To[i]==pre) continue; G[u][0]++; dfs(To[i],u); } } int main() { int T,n,i,x,y,q,Case=0; scanf("%d",&T); while(T--){ printf("Case #%d: ",++Case); init(); scanf("%d",&n); for(i=1;i<=n;i++) G[i].clear(); for(i=1;i<n;i++){ scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1,0); scanf("%d",&q); while(q--){ scanf("%d",&x); if(x==1) printf("%d ",ans); else { scanf("%d%d",&x,&y); change(x,y); } } } return 0; }