传送门（下面也有题面）
题目大意：
一颗有根树，每个非叶子节点都有三个子节点，每个节点的权为0/1。
每个节点的权 取决于其所有子节点中 哪种权出现的次数更多。
有若干次询问，每次询问修改一个叶子节点的权，然后输出修改后根节点的权。
给出叶子节点初始值。
解法：树链剖分+线段树
叶子节点和非叶子节点的性质不同，为了省却麻烦，我们把叶子节点去掉，
每次修改叶子节点就直接修改其父亲。以下的“叶子节点”均指处理后的树的叶子节点。
如果用num[]记录每个节点的权为1的子节点个数，
那么当num[i]>1时，点i权为1；当num[i]<=1时，权为0。
记fa[i]表示i节点的父亲节点。
可以推出：
当num[i]=1时num[i]++,那么num[fa[i]]++;
当num[i]=2时num[i]--，那么num[fa[i]]--;
于是就有一个暴力算法，如果修改的当前点的num满足条件，就向上修改。
其实就相当于使从根到叶子节点的链上最后一个num！=1(2)的点到叶子节点的区间权值+(-)1;
然后就可以用树链剖分+线段树愉快的AC了。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N ((1<<19)-1) 4 5 int n,cnt; 6 int fir[N],size[N],pt[N],pos[N],fa[N<<2],data[N<<2],ori[N]; 7 8 struct edge{ 9 int to,n; 10 edge(){} edge(int _to,int _n){to=_to,n=_n;} 11 }; 12 vector<edge>e; 13 14 struct SN{ 15 int num,flag; 16 SN*son[2]; 17 }sn[N<<2],*root; 18 19 void putin() 20 { 21 int i,j,x; 22 scanf("%d",&n); 23 e.push_back(edge()); 24 for (i=1;i<=n;i++) 25 for (j=0;j<3;j++) 26 { 27 scanf("%d",&x); 28 fa[x]=i; 29 if (x<=n) 30 { 31 e.push_back(edge(x,fir[i])); 32 fir[i]=e.size()-1; 33 } 34 } 35 } 36 37 void pre(int x) 38 { 39 size[x]=1;pt[x]=0; 40 for (int i=fir[x];i;i=e[i].n) 41 { 42 pre(e[i].to); 43 size[x]+=size[e[i].to]; 44 if (size[e[i].to]>size[pt[x]]) pt[x]=e[i].to; 45 } 46 } 47 48 void getpath(int x) 49 { 50 pos[x]=++cnt; 51 if (pt[x]) 52 { 53 ori[pt[x]]=ori[x]; 54 getpath(pt[x]); 55 } 56 for (int i=fir[x];i;i=e[i].n) 57 { 58 if (e[i].to==pt[x]) continue; 59 ori[e[i].to]=e[i].to; 60 getpath(e[i].to); 61 } 62 } 63 64 void build(SN&x,int l,int r) 65 { 66 x.flag=-1; 67 if (l==r) return; 68 x.son[0]=&sn[++cnt]; 69 x.son[1]=&sn[++cnt]; 70 int m=(l+r)>>1; 71 build(*x.son[0],l,m); 72 build(*x.son[1],m+1,r); 73 } 74 75 void update(SN&x) 76 { 77 for (int i=0;i<2;i++) 78 { 79 SN&z=*x.son[i]; 80 z.num=z.flag=x.flag; 81 } 82 x.flag=-1; 83 } 84 85 bool change(SN&x,int l,int r,int i,int j,int &p,int &v) 86 { 87 if (i<=l&&r<=j&&x.num==p) 88 { 89 x.num+=v; 90 x.flag=x.num; 91 return 0; 92 } 93 if (l==r) 94 { 95 x.num+=v; 96 return 1; 97 } 98 if (x.flag!=-1) update(x); 99 int m=(l+r)>>1; 100 bool re=0; 101 if (m<j) re=change(*x.son[1],m+1,r,i,j,p,v); 102 if (!re&&i<=m) re=change(*x.son[0],l,m,i,j,p,v); 103 x.num=-1; 104 if ((*x.son[0]).num==(*x.son[1]).num)x.num=(*x.son[0]).num; 105 return re; 106 } 107 108 void work(int x) 109 { 110 int p,v; 111 if (data[x]) 112 { 113 data[x]=0; 114 p=2,v=-1; 115 } 116 else 117 { 118 data[x]=1; 119 p=1,v=1; 120 } 121 x=fa[x]; 122 while (x) 123 { 124 if (change(*root,1,n,pos[ori[x]],pos[x],p,v)) return; 125 x=fa[ori[x]]; 126 } 127 } 128 129 void initialize() 130 { 131 int x; 132 for (int i=n+1;i<=3*n+1;i++) 133 { 134 scanf("%d",&x); 135 if (x) work(i); 136 } 137 } 138 139 int SR(SN&x,int r) 140 { 141 if (r==1) return x.num; 142 if (x.flag!=-1) update(x); 143 return SR(*x.son[0],(1+r)>>1); 144 } 145 146 void respond() 147 { 148 int q,x,temp; 149 scanf("%d",&q); 150 for (int i=0;i<q;i++) 151 { 152 scanf("%d",&x); 153 work(x); 154 temp=SR(*root,n); 155 if (temp>1) printf("%d\n",1); 156 else printf("%d\n",0); 157 } 158 } 159 160 int main() 161 { 162 putin(); 163 pre(1); 164 ori[1]=1; 165 getpath(1); 166 cnt=0; 167 root=&sn[0]; 168 build(*root,1,n); 169 initialize(); 170 respond(); 171 }
说好的题面：
计算神经学作为新兴的交叉学科近些年来一直是学术界的热点。一种叫做SHOI 的神经组织因为其和近日发现的化合物 SHTSC 的密切联系引起了人们的极大关注。
SHOI 组织由若干个 SHOI 细胞构成,SHOI 细胞之间形成严密的树形结构。
每个 SHOI 细胞都有且只有一个输出端,被称为轴突,除了一个特殊的、被称为根细胞的 SHOI
细胞的输出作为整个组织的输出以外,其余细胞的轴突均连向其上级 SHOI
细胞;并且有且只有三个接收端,被称为树突,从其下级细胞或者其它神经组织那里接收信息。SHOI 细胞的信号机制较为简单,仅有 0 和 1
两种。每个 SHOI 细胞根据三个输入端中 0 和 1 信号的多寡输出较多的那一种。
现在给出了一段 SHOI 组织的信息,以及外部神经组织的输入变化情况。请你模拟 SHOI 组织的输出结果。
第一行一个整数:n。表示 SHOI 组织的总细胞个数。SHOI 细胞由 1~n 编号,编号为 1 的是根细胞。
从第二行开始的 n 行,每行三个整数 x1, x2, x3,分别表示编号为 1~n 的 SHOI 细胞的树突连接。1<xi≤n
表示连向编号为 xi 的细胞的轴突, n<xi≤3n+1 表示连向编号为 xi 的外界输入。输入数据保证给出的 SHOI
组织是合法的且所有的 xi 两两不同。
接下来一行 2n+1 个 0/1 的整数,表示初始时的外界输入。
第 n+3 行有一个整数:q,表示总操作数。
之后 q 行每行一个整数 x,表示编号为 x 的外界输入发生了变化。
输出 q 行每行一个整数,对应第 i 次外界输入变化后的根细胞的输出。
对于 100%的数据,n≤500000,q≤500000。
原文：http://www.cnblogs.com/KaNNeXFF/p/5503301.html
