Codeforces 1017G The Tree 题目大意： 给一个一开始所有节点都是白色的树，给一些查询操作，给的三种操作：
1.在v的所有子节点中向下深搜，直到找到第一个白色子孙节点（或者自己），染成黑色。
2.把v的所有子树（包括它自己）全部染白。
3.输出v节点的颜色。
思路： 一般想到就是大模拟，直接暴力深搜Q次，操作3是O(1),其他都是O(n),时间复杂度总的就是。。。。O( nqn q ),Boom~
所以看了看官方题解，毕竟这个是相当于Div1 E题难度的题目，我这种接近Newbie警告的pupil，怎么可能会写。。。但是看过官方题解觉得好像不难啊，就决定花一个早上研究了一下写掉了，而且发现标程里面有些东西是不太必要的，比如那个存放原本状态的old_black数组。初始化我改用了memset，比for循环稍好，并且不像标程一样每一个V2数组都要重新初始化，我只初始化本轮查询需要用到的就可以了。然而。。。并没有什么卵用，总的思路和标程是一样一样的。
总的思路是对查询分块建立一棵小树，只存放被查询到的点，并记录被查询到的节点间白色块的数量，在小树上DFS进行三种操作，直到该块查询全部预处理完成后再将更新应用到整棵树上。总的时间复杂度一下子就降到了O( nn??√n n )级别
主要节省的时间在两个地方：
1.分块后，每块查询的时候，并不需要每次遍历每个节点，跳过了一些无关紧要的节点最后再更新。
2.有些重复的操作，预处理的时候就能避免掉，比如对同一个节点反复进行操作2的清空，或者一直间或染黑染白。
代码（带详细的注释（虽然图方(zhuang)便(bi)全都是英文）

#include #include #include #include using namespace std; struct mini//the data structure storing edges of the mini-tree { int to; //the son vertex int white; //the number of white vertices between two vertices we need to operate in the mini-tree int dis; //the distance between two mini-tree vertices in the original tree, we need this to do the operation 2 }; int v[100005]; //the vertex we need to operate int t[100005]; //the type of operation we do vector edge[100005]; //the origin tree, which has no weight on its edges. So we just need to storage its end. vector minitree[100005]; // A mini Tree, with a weighted edge bool vis[100005]; //mark the vertex if we need to add the vertex to the mini-tree bool cl[100005]; //mark if the clear operation should be done bool isblack[100005]; //mark the vertex. isblack[i] is true when i-th vertex is black int pusher[100005]; //check how many operation 1s should be done to the son void builder(int now,int pre,int white,int dis) { //cout<minitree[now][i].white) { minitree[now][i].white=0; //this doesn't matter, the white value won't be used any more this round (because both of the vertices are marked black,you may never go to line 62,where is the only line which need this value again.),but we know, in this situation, it's natural to think that no vertices between the father and the son are white op1(minitree[now][i].to); //if the operation 1 was done more than the white vertices between two key vertices, just do it for his son } } } }void op2(int now) { isblack[now]=false; pusher[now]=0; //all the sons are marked white, so all the pushes we made were abandoned cl[now]=true; for(int i=0; i0) { isblack[now]=true; push--; } } for(int i=0; i>n>>q; for(int i=2; i<=n; i++) { int temp; cin>>temp; edge[temp].push_back(i); } for(int i=1; i<=q; i++) { cin>>t[i]>>v[i]; } memset(isblack,0,sizeof(isblack)); //all the vertices were white before we do the operations int block=sqrt(n); for(int i=1; i<=q; i+=block)//Block the queries into pieces, one loop O(n+sqrt(n)+sqrt(n)+n),totally O(2(n+n*sqrt(n))) {memset(vis,0,sizeof(vis)); //memset() is a little bit faster than the O(n) for loop, but still O(n) memset(cl,0,sizeof(cl)); memset(pusher,0,sizeof(pusher)); for(int j=0; j