题意：
扔个现在可以交题的链接：?pid=2146
就是给出一个n个点的有根树，和m次操作；
初始时树上所有结点权值均为0；
1操作将根到x结点的所有结点权值置为1，并输出这次修改了多少个元素；
2操作将x结点的子树中所有结点权值置为0，并输出这次修改了多少个元素；
n，m<=100000；
题解：
1操作显然是树链剖分的形式，利用线段树维护区间修改查询；
单次操作复杂度O(log^2n)也是支持的；
2操作有点难度，一开始没想出来，以为是还要另维护dfs序什么的；
但是实际上树剖过程中已经维护一个dfs序了，只需要在第二次dfs中记录一个区间右端点；
这样直接就可以在线段树上搞，单次复杂度O(logn)；
然后，就，，解决了！
所以day1究竟是水成了什么样子= =；
然而自己做的时候手滑了，因为点的标号从0开始；
有一点地方和平时写的不太一样，维护重链错了时间似乎退化到了O(n^2)；
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 110000#define lson l,mid,no<<1#define rson mid+1,r,no<<1|1using namespace std;int to[N],next[N],head[N],cnt;int size[N],deep[N],top[N],fa[N];int son[N],l[N],r[N],rank[N],tot,n;int sum[N<<2];bool cov[N<<2],flag[N<<2];char str[100];void add(int x,int y){to[++cnt]=y;next[cnt]=head[x];head[x]=cnt;}void dfs1(int x,int pre,int d){fa[x]=pre,deep[x]=d,size[x]=1;int i,y,ma;for(i=head[x],ma=0;i;i=next[i]){if((y=to[i])!=pre){dfs1(y,x,d+1);size[x]+=size[y];if(ma<size[y])son[x]=y,ma=size[y];}}}void dfs2(int x,int t){top[x]=t,l[x]=++tot,rank[tot]=x;if(son[x])dfs2(son[x],t);int i,y;for(i=head[x];i;i=next[i])if((y=to[i])!=fa[x]&&y!=son[x])dfs2(y,y);r[x]=tot;}void Pushup(int no){sum[no]=sum[no<<1]+sum[no<<1|1];}void Pushdown(int no,int len){if(cov[no]){cov[no<<1]=cov[no<<1|1]=1;flag[no<<1]=flag[no<<1|1]=flag[no];sum[no<<1]=flag[no]?len-(len>>1):0;sum[no<<1|1]=flag[no]?len>>1:0;cov[no]=0;}}void update(int l,int r,int no,int st,int en,bool val){if(st<=l&&r<=en){cov[no]=1;flag[no]=val;sum[no]=(r-l+1)*val;}else{int mid=(l+r)>>1;Pushdown(no,r-l+1);if(en<=mid)update(lson,st,en,val);else if(st>mid)update(rson,st,en,val);elseupdate(lson,st,en,val),update(rson,st,en,val);Pushup(no);}}int query(int l,int r,int no,int st,int en){if(st<=l&&r<=en)return sum[no];else{int mid=(l+r)>>1;Pushdown(no,r-l+1);if(en<=mid)return query(lson,st,en);else if(st>mid)return query(rson,st,en);elsereturn query(lson,st,en)+query(rson,st,en);}}int slove1(int x){int y=0,ret=0;while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);ret+=l[x]-l[top[x]]+1-query(1,n,1,l[top[x]],l[x]);update(1,n,1,l[top[x]],l[x],1);x=fa[top[x]];}if(deep[x]<deep[y])swap(x,y);ret+=l[x]-l[y]+1-query(1,n,1,l[y],l[x]);update(1,n,1,l[y],l[x],1);return ret;}int slove2(int x){int ret=query(1,n,1,l[x],r[x]);update(1,n,1,l[x],r[x],0);return ret;}int main(){int m,i,j,k,x,y;scanf("%d",&n);for(i=1;i<n;i++){scanf("%d",&x);add(x,i);}dfs1(0,-1,0);dfs2(0,-1);scanf("%d",&m);for(i=1;i<=m;i++){scanf("%s%d",str,&x);if(str[0]=='i')printf("%d\n",slove1(x));elseprintf("%d\n",slove2(x));}return 0;}
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
