1.前向星型模板
/* 重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。 轻儿子：v的其它子节点。 重边：点v与其重儿子的连边。 轻边：点v与其轻儿子的连边。 重链：由重边连成的路径。 轻链：轻边。 */const int MAXN = 50000+10; struct node { int to, next; node(){ } node(int to, int next) : to(to), next(next){ } }edge[2*MAXN]; int head[MAXN], alledge; void init() { memset(head, 0xff, sizeof(head)); alledge = 0; } void addedge(int x, int y) { edge[alledge] = node(y, head[x]); head[x] = alledge++; edge[alledge] = node(x, head[y]); head[y] = alledge++; } int a[MAXN];//点权值 int siz[MAXN];//siz[v]表示以v为根的子树的节点数(包含自身结点) int dep[MAXN];//dep[v]表示v的深度(根深度为1) int fa[MAXN];//fa[v]表示v的父亲 int son[MAXN];//son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子） int top[MAXN];//top[v]表示v所在的链的顶端节点 int w[MAXN];//w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置 int totw; void init_treelist() { memset(son, 0xff, sizeof(son));// son[v]为 -1 表示重儿子不存在 memset(top, 0xff, sizeof(top)); totw = 0; } void dfs_1(int id, int pr, int deep)//求 fa、dep、siz、son、top { fa[id] = pr; dep[id] = deep; siz[id] = 1; int s = -1, ii = -1; for(int i = head[id]; ~i; i = edge[i].next) { int to = edge[i].to; if(to == pr) continue; dfs_1(to, id, deep+1); siz[id] += siz[to]; if(siz[to] > s) { s = siz[to]; ii = to; } } son[id] = ii; } void dfs_2(int id, int pr)//求 w { w[id] = ++totw; if(top[id]==-1) top[id] = id; if(~son[id]) { top[son[id]] = top[id]; dfs_2(son[id], id); } for(int i = head[id]; ~i; i = edge[i].next) { int to = edge[i].to; if(to == pr) continue; if(to == son[id]) continue; dfs_2(to, id); } } void update(int x, int y, int k) { int fx = top[x], fy = top[y]; while(fx != fy) { if(dep[fx] < dep[fy]) { swap(fx, fy); swap(x, y); } //update(1, 1, n, w[fx], w[x], k); 线段树更新 x = fa[fx]; fx = top[x]; } if(dep[x] < dep[y]) { swap(x, y); } //update(1, 1, n, w[y], w[x], k); 线段树更新 } int main (void) { /* 建图 */ dfs_1(1, -1, 1); dfs_2(1, -1); }
顺附 codefroces 343D - Water Tree AC代码
/* 重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。 轻儿子：v的其它子节点。 重边：点v与其重儿子的连边。 轻边：点v与其轻儿子的连边。 重链：由重边连成的路径。 轻链：轻边。 */ #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; const int MAXN = 500000+10; int n; struct node { int to, next; node(){ } node(int to, int next) : to(to), next(next){ } }edge[2*MAXN]; int head[MAXN], alledge; void init() { memset(head, 0xff, sizeof(head)); alledge = 0; } void addedge(int x, int y) { edge[alledge] = node(y, head[x]); head[x] = alledge++; edge[alledge] = node(x, head[y]); head[y] = alledge++; } int siz[MAXN];//siz[v]表示以v为根的子树的节点数(包含自身结点) int dep[MAXN];//dep[v]表示v的深度(根深度为1) int fa[MAXN];//fa[v]表示v的父亲 int son[MAXN];//son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子） int top[MAXN];//top[v]表示v所在的链的顶端节点 int w[MAXN];//w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置 int End[MAXN], END; int totw; void init_treelist() { memset(son, 0xff, sizeof(son));// son[v]为 -1 表示重儿子不存在 memset(top, 0xff, sizeof(top)); totw = 0; } void dfs_1(int id, int pr, int deep)//求 fa、dep、siz、son、top { fa[id] = pr; dep[id] = deep; siz[id] = 1; int s = -1, ii = -1; for(int i = head[id]; ~i; i = edge[i].next) { int to = edge[i].to; if(to == pr) continue; dfs_1(to, id, deep+1); siz[id] += siz[to]; if(siz[to] > s) { s = siz[to]; ii = to; } } son[id] = ii; } void dfs_2(int id, int pr)//求 w { w[id] = ++totw; END = id; if(top[id]==-1) top[id] = id; if(~son[id]) { top[son[id]] = top[id]; dfs_2(son[id], id); } for(int i = head[id]; ~i; i = edge[i].next) { int to = edge[i].to; if(to == pr) continue; if(to == son[id]) continue; dfs_2(to, id); } End[id] = END; } struct treenode { int v; int flag; }tree[MAXN<<2]; void bulid_tree() { memset(tree, 0x00, sizeof(tree)); } void push_down(int id) { tree[id<<1].flag = tree[id].flag; tree[(id<<1)|1].flag = tree[id].flag; tree[id].flag = 0; } void update(int id, int l, int r, int left, int right, int k) { if(l==left && r==right) { if(k==0) tree[id].flag = -1; if(k==1) tree[id].flag = 1; if(l==r) tree[id].v = k; return ; } int mid = l+r>>1; if( tree[id].flag ) push_down(id); if(right <= mid) { update(id<<1, l, mid, left, right, k); } else if(left > mid) { update((id<<1)|1, mid+1, r, left, right, k); } else { update(id<<1, l, mid, left, mid, k); update((id<<1)|1, mid+1, r, mid+1, right, k); } } int query(int id, int l, int r, int index) { if(tree[id].flag == -1) return 0; if(tree[id].flag == 1) return 1; if(l==r&& r==index) return tree[id].v; int mid = l+r>>1; if(index <= mid) return query(id<<1, l, mid, index); return query((id<<1)|1, mid+1, r, index); } void update(int x, int y, int k) { int fx = top[x], fy = top[y]; while(fx != fy) { if(dep[fx] < dep[fy]) { swap(fx, fy); swap(x, y); } update(1, 1, n, w[fx], w[x], k); x = fa[fx]; fx = top[x]; } if(dep[x] < dep[y]) { swap(x, y); } update(1, 1, n, w[y], w[x], k); } int main (void) { ios::sync_with_stdio(false); init(); init_treelist(); cin >> n; for(int i = 1; i < n; ++i) { int x, y; cin >> x >> y; addedge(x, y); } dfs_1(1, -1, 1); dfs_2(1, -1); int q; cin >> q; while(q--) { int c, x; cin >> c >> x; switch( c ) { case 1: update(1, 1, n, w[x], w[End[x]], 1); break; case 2: update(1, x, 0); break; default : cout << query(1, 1, n, w[x]) << endl; break; } } return 0; }