题目一 : SPOJ 375 Query On a Tree
http://www.spoj.com/problems/QTREE/
给一个树，求a,b路径上最大边权，或者修改a,b边权为t。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm> using namespace std;
const int maxn = + ; int N,pos=;
char ss[]; struct SegmentTree{
int l,r,flag;
int maxv,minv;
}Node[maxn * ]; int e[maxn][];
int size[maxn],dep[maxn],top[maxn],son[maxn];
int fa[maxn],Segnum[maxn],Treenum[maxn]; int tot = ;
int first[maxn],next[maxn*];
int u[maxn*],v[maxn*]; void clear();
void change(int&,int&);
void Add(int,int);
void dfs_1(int,int,int);
void dfs_2(int,int);
void build(int,int,int);
void update(int,int,int,int);
int query(int,int,int);
int find_max(int,int);
void rever(int,int,int);
void get_rever(int,int);
void pushdown(int);
void pushup(int); int main(){
int tcase;
scanf("%d",&tcase);
while(tcase --){
clear();
int x,y,z;
scanf("%d",&N);
for(int i = ;i < N;++ i){
scanf("%d%d%d",&e[i][],&e[i][],&e[i][]);
Add(e[i][],e[i][]);
Add(e[i][],e[i][]);
} dfs_1(,,);
dfs_2(,);
build(,,N);
for(int i = ;i < N;++ i){
if(dep[e[i][]] > dep[e[i][]])
swap(e[i][],e[i][]);
update(,Segnum[e[i][]],Segnum[e[i][]],e[i][]);
}
while(){
scanf("%s",ss);
if(ss[] == 'D')
break;
scanf("%d%d",&x,&y);
if(ss[] == 'C'){
update(,Segnum[e[x][]],Segnum[e[x][]],y);
}
else if(ss[] == 'Q'){
printf("%d\n",find_max(x,y));
}
else if(ss[] == 'N'){
get_rever(x,y);
}
}
}
return ;
} void clear(){
pos = ;tot = ;
memset(son,,sizeof son);
memset(first,,sizeof first);
}
void Add(int s,int t){
++ tot;
u[tot] = s;v[tot] = t;
next[tot] = first[u[tot]];
first[u[tot]] = tot;
}
void dfs_1(int now,int f,int depth){
size[now] = ;
fa[now] = f;
dep[now] = depth; for(int i = first[now];i;i = next[i]){
if(v[i] != f){
dfs_1(v[i],now,depth + );
size[now] += size[v[i]];
if(!son[now] || size[v[i]] > size[son[now]])
son[now] = v[i];
}
}
return;
} void dfs_2(int now,int ances){
top[now] = ances;
Segnum[now] = ++ pos;
Treenum[Segnum[now]] = now; if(!son[now])return;
dfs_2(son[now],ances); for(int i = first[now];i;i = next[i]){
if(v[i] != son[now] && v[i] != fa[now]){
dfs_2(v[i],v[i]);
}
}
return;
} void build(int o,int l,int r){
Node[o].l = l;
Node[o].r = r;
Node[o].minv = Node[o].maxv = ;
Node[o].flag = ;
if(l == r)
return;
int Mid = (l + r) >> ;
build(o<<,l,Mid);
build(o<<|,Mid+,r);
} void update(int o,int l,int r,int v){
if(Node[o].l == l && Node[o].r == r){
Node[o].minv = Node[o].maxv = v;
Node[o].flag = ;
return;
}
int Mid = (Node[o].l + Node[o].r) >> ;
pushdown(o);
if(r <= Mid)
update(o<<,l,r,v);
else if(l > Mid)
update(o<<|,l,r,v);
pushup(o);
}
void pushdown(int o){
if(Node[o].l == Node[o].r)
return;
int lc = o << ,rc = o << | ;
if(Node[o].flag){
Node[o].flag = ;
Node[lc].flag ^= ;
Node[rc].flag ^= ;
change(Node[rc].minv,Node[rc].maxv);
change(Node[lc].maxv,Node[lc].minv);
}
}
void pushup(int o){
int lc = o << ,rc = o << | ;
Node[o].maxv = max(Node[lc].maxv,Node[rc].maxv);
Node[o].minv = min(Node[lc].minv,Node[rc].minv);
} int query(int o,int l,int r){
if(Node[o].l == l && Node[o].r == r){
return Node[o].maxv;
}
int Mid = (Node[o].l + Node[o].r) >> ;
pushdown(o);
if(r <= Mid)
return query(o<<,l,r);
else if(l > Mid)
return query(o<<|,l,r);
else
return max(query(o<<,l,Mid),query(o<<|,Mid+,r));
pushup(o);
}
void rever(int o,int l,int r){
if(Node[o].l == l && Node[o].r == r){
change(Node[o].maxv,Node[o].minv);
Node[o].flag ^= ;
return;
}
int Mid = (Node[o].l + Node[o].r) >> ;
pushdown(o);
if(r <= Mid)
rever(o<<,l,r);
else if(l > Mid)
rever(o<<|,l,r);
else{
rever(o<<,l,Mid);
rever(o<<|,Mid+,r);
}
pushup(o);
}
int find_max(int x,int y){
int f1 = top[x],f2 = top[y];
int ret = -; while(f1 != f2){
if(dep[f1] < dep[f2]){
swap(f1,f2);
swap(x,y);
}
ret = max(ret,query(,Segnum[f1],Segnum[x]));
x = fa[f1];f1 = top[x];
} if(x == y)return ret;
if(dep[x] < dep[y]){
ret = max(ret,query(,Segnum[son[x]],Segnum[y]));
}
else{
ret = max(ret,query(,Segnum[son[y]],Segnum[x]));
} return ret;
} void get_rever(int x,int y){
int f1 = top[x],f2 = top[y]; while(f1 != f2){
if(dep[f1] < dep[f2]){
swap(f1,f2);
swap(x,y);
}
rever(,Segnum[f1],Segnum[x]);
x = fa[f1];f1 = top[x];
}
if(x == y)return;//如果是针对边的操作， 这个东西不能少。。
if(dep[x] < dep[y]){
rever(,Segnum[son[x]],Segnum[y]);//如果是边权，注意这里的写法。要下放。
}
else{
rever(,Segnum[son[y]],Segnum[x]);
}
return;
} void change(int &a,int &b){
int tp1 = a,tp2 = b;
a = -tp2;b = -tp1;
return;
}
树链剖分
TLE的但是保证 不WA的LCT
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream> using namespace std;
const int N = + ; int n;
int top, st[N << ];
int fa[N], c[N][], val[N], mx[N];
bool rev[N]; void pushup(int x) {
int l = c[x][], r = c[x][];
mx[x] = x;
if(l && val[mx[l]] > val[mx[x]]) mx[x] = mx[l];
if(r && val[mx[r]] > val[mx[x]]) mx[x] = mx[r];
} void pushdown(int x) {
int l = c[x][], r = c[x][];
if(rev[x]) {
rev[x] ^= ; rev[l] ^= ; rev[r] ^= ;
swap(c[x][], c[x][]);
}
} bool isroot(int x) {
return c[fa[x]][] != x && c[fa[x]][] != x;
} void rotate(int x) {
int y = fa[x], z = fa[y], l, r;
if(c[y][] == x) l = , r = ;
else l = , r = ;
if(!isroot(y)) {
if(c[z][] == y) c[z][] = x;
else c[z][] = x;
}
fa[x] = z; fa[y] = x; fa[c[x][r]] = y;
c[y][l] = c[x][r]; c[x][r] = y;
pushup(y); pushup(x);
} void splay(int x) {
top = ; st[++ top] = x;
for(int i = x; !isroot(i); i = fa[i])
st[++ top] = fa[i];
while(top) pushdown(st[top --]);
while(!isroot(x)) {
int y = fa[x], z = fa[y];
if(!isroot(y)) {
if((c[z][] == y) ^ (c[y][] == x)) rotate(x);
else rotate(y);
}
rotate(x);
}
pushup(x);
} void access(int x) {
int t = ;
while(x) {
splay(x); c[x][] = t;
t = x;
pushup(x); x = fa[x];
}
} void mroot(int x) {
access(x); splay(x); rev[x] ^= ;
} void link(int a, int b) {
mroot(a); fa[a] = b;
} void cut(int a, int b) {
mroot(a); access(b); splay(b);
c[b][] = fa[c[b][]] = ;
} int Q(int a, int b) {
mroot(a); access(b); splay(b);
return val[mx[b]];
} void C(int a, int b) {
access(a + n); splay(a + n);
val[a + n] = b;
} int main() {
char ss[];
int a, b, t, cs;
scanf("%d", &t);
while(t --) {
memset(fa, , sizeof fa);
memset(rev, , sizeof rev);
memset(c, , sizeof c);
memset(mx, , sizeof mx);
memset(val, , sizeof val);
scanf("%d", &n);
for(int i = ; i < n; ++ i) {
scanf("%d%d%d", &a, &b, &cs);
val[i + n] = cs;
mx[i + n] = i + n;
link(a, i + n); link(b, i + n);
}
while() {
scanf("%s", ss);
if(ss[] == 'D') break;
if(ss[] == 'C') {
scanf("%d%d", &a, &b);
C(a, b);
}
else {
scanf("%d%d", &a, &b);
printf("%d\n", Q(a, b));
}
}
}
return ;
}
lct
题目二： SPOJ Query On a Tree II
题目大意：
给一个树，两个操作，求a->b距离，求a->b路径上的第k个点。
算法讨论：
用LCA来维护，第k个点也用Lca来跳就可以啦。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; const int N = + ; int n, cnt;
int head[N], fa[N], f[N][];
int dis[N], depth[N]; struct Edge {
int from, to, dis, next;
}edges[N << ]; void insert(int from, int to, int w) {
++ cnt;
edges[cnt].from = from; edges[cnt].to = to; edges[cnt].dis = w;
edges[cnt].next = head[from]; head[from] = cnt;
} void build(int u, int f) {
fa[u] = f;
for(int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
if(v != f) {
dis[v] = dis[u] + edges[i].dis;
depth[v] = depth[u] + ;
build(v, u);
}
}
} void prepare() {
memset(f, -, sizeof f);
for(int i = ; i <= n; ++ i) f[i][] = fa[i];
for(int j = ; ( << j) <= n; ++ j) {
for(int i = ; i <= n; ++ i) {
if(f[i][j - ] != -) {
f[i][j] = f[f[i][j - ]][j - ];
}
}
}
} int lca(int a, int b) {
int i;
if(depth[a] < depth[b]) swap(a, b);
for(i = ; ( << i) <= depth[a]; ++ i);
-- i;
for(int j = i; j >= ; -- j) {
if(depth[a] - depth[b] >= ( << j))
a = f[a][j];
}
if(a == b) return a;
for(int j = i; j >= ; -- j) {
if(f[a][j] != - && f[a][j] != f[b][j]) {
a = f[a][j]; b = f[b][j];
}
}
return f[a][];
} int splca(int a, int len) {
int i;
for(i = ; ( << i) <= depth[a]; ++ i);
-- i;
for(int j = i; j >= ; -- j) {
if(depth[a] - len >= ( << j)) {
a = f[a][j];
}
}
return a;
} int Q(int a, int b) {
return dis[a] + dis[b] - * dis[lca(a, b)];
} int K(int a, int b, int c) {
int Lca = lca(a, b), res;
if(depth[a] - depth[Lca] + >= c) {
res = splca(a, depth[Lca] + (depth[a] - depth[Lca]) - c + );
}
else {
c -= (depth[a] - depth[Lca]);
res = splca(b, depth[Lca] + c - );
}
return res;
} void clear() {
cnt = ;
memset(head, , sizeof head);
} int main() {
int t, u, v, w, a, b, c;
char ss[];
bool flag = false;
scanf("%d", &t);
while(t --) {
if(flag) puts("");
flag = true;
clear();
scanf("%d", &n);
for(int i = ; i < n; ++ i) {
scanf("%d%d%d", &u, &v, &w);
insert(u, v, w); insert(v, u, w);
}
depth[] = ;
dis[] = ;
build(, );
prepare();
while() {
scanf("%s", ss);
if(ss[] == 'D') {
if(ss[] == 'O') break;
else {
scanf("%d%d", &a, &b);
printf("%d\n", Q(a, b));
}
}
else {
scanf("%d%d%d", &a, &b, &c);
printf("%d\n", K(a, b, c));
}
}
}
return ;
}
Q2 LCA版
题目三 SPOJ Query On a Tree III
题目大意：
给出一棵树，每个点有权值，而且互不相同。求以某个点为根的子树中第k小的权值是哪个点。
算法讨论：
我的第一个做法是可持久化线段树 + 区间第K小值。我们知道一个点的子树在DFS序中一定是连续的，所以我们可以查询这个区间的第K小值。这就是可持久化线段树的应用。注意可持久化线段树是NlogN的空间，我居然忘记了，只开了原来的4倍。。。所以有三个点re了。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; const int N = + ; int n, m, cnt, tot, pos;
int fa[N], size[N], num[N], mx[N], w[N];
int root[N], rank[N], son[N], head[N], seg[N]; struct Edge {
int from, to, next;
}edges[N << ]; struct SegTree {
int l, r, size;
}Node[N * ];//注意可持久化线段树是NlogN的空间 struct data {
int v, pos, id;
bool operator < (const data &k) const {
return v < k.v;
}
}a[N]; void insert(int from, int to) {
++ cnt;
edges[cnt].from = from; edges[cnt].to = to;
edges[cnt].next = head[from]; head[from] = cnt;
} void dfs_1(int x, int f) {
size[x] = ;
fa[x] = f;
for(int i = head[x]; i; i = edges[i].next) {
int v = edges[i].to;
if(v != f) {
dfs_1(v, x);
size[x] += size[v];
if(!son[x] || size[v] > size[son[x]])
son[x] = v;
}
}
} void dfs_2(int x, int ances) {
mx[x] = num[x] = ++ pos;
seg[pos] = x;
if(!son[x]) return;
dfs_2(son[x], ances);
mx[x] = max(mx[x], mx[son[x]]);
for(int i = head[x]; i; i = edges[i].next) {
int v = edges[i].to;
if(v != fa[x] && v != son[x]) {
dfs_2(v, v);
mx[x] = max(mx[x], mx[v]);
}
}
} void build(int &o, int l, int r) {
o = ++ tot;
Node[o].l = Node[o].r = Node[o].size = ;
if(l >= r) return;
int mid = (l + r) >> ;
build(Node[o].l, l, mid);
build(Node[o].r, mid + , r);
} void update(int pre, int &o, int l, int r, int kth) {
o = ++ tot;
Node[o] = Node[pre];
Node[o].size ++;
if(l >= r) return;
int mid = (l + r) >> ;
if(kth <= mid)
update(Node[pre].l, Node[o].l, l, mid, kth);
else
update(Node[pre].r, Node[o].r, mid + , r, kth);
} int query(int r1, int r2, int l, int r, int kth) {
if(l >= r) return l;
int lc = Node[Node[r2].l].size - Node[Node[r1].l].size;
int mid = (l + r) >> ;
if(lc >= kth) {
int ans = query(Node[r1].l, Node[r2].l, l, mid, kth);
return ans;
}
else {
int ans = query(Node[r1].r, Node[r2].r, mid + , r, kth - lc);
return ans;
}
} int Q(int x, int k) {
int l = num[x], r = mx[x];
return a[query(root[l - ], root[r], , n, k)].id;
} int main() {
int u, v, x, k;
scanf("%d", &n);
for(int i = ; i <= n; ++ i) scanf("%d", &w[i]);
for(int i = ; i < n; ++ i) {
scanf("%d%d", &u, &v);
insert(u, v); insert(v, u);
}
dfs_1(, ); dfs_2(, );
for(int i = ; i <= n; ++ i) {
a[i].v = w[seg[i]];
a[i].pos = i;
a[i].id = seg[i];
}
sort(a + , a + n + );
for(int i = ; i <= n; ++ i) {
rank[a[i].pos] = i;
}
build(root[], , n);
for(int i = ; i <= n; ++ i) {
update(root[i - ], root[i], , n, rank[i]);
}
scanf("%d", &m);
for(int i = ; i <= m; ++ i) {
scanf("%d%d", &x, &k);
printf("%d\n", Q(x, k));
}
return ;
}
可持久化线段树+树剖
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> using namespace std; const int N = + ; int n, m, cnt, tot, pos;
int fa[N], num[N], mx[N], w[N], st[N << ];
int root[N], rank[N], head[N], seg[N], fast[N]; struct Edge {
int from, to, next;
}edges[N << ]; struct SegTree {
int l, r, size;
}Node[N * ]; struct data {
int v, pos, id;
bool operator < (const data &k) const {
return v < k.v;
}
}a[N]; //seg[i] the ith pos is seg[i]
//num[i] the i's pos in the segment tree.
void dfs() {
int top = ;
st[++ top] = ;
while(top) {
int now = st[top], f = fast[top];
top --;
if(!num[now]) {
num[now] = ++ pos;
mx[now] = num[now];
st[++ top] = now;
fa[now] = f;
for(int i = head[now]; i; i = edges[i].next) {
if(edges[i].to != f) {
st[++ top] = edges[i].to;
fast[top] = now;
}
}
}
}
for(int i = ; i <= n; ++ i)
seg[num[i]] = i;
for(int i = n; i >= ; -- i) {
mx[fa[seg[i]]] = max(mx[seg[i]], mx[fa[seg[i]]]);
}
} void insert(int from, int to) {
++ cnt;
edges[cnt].from = from; edges[cnt].to = to;
edges[cnt].next = head[from]; head[from] = cnt;
} void build(int &o, int l, int r) {
o = ++ tot;
Node[o].l = Node[o].r = Node[o].size = ;
if(l >= r) return;
int mid = (l + r) >> ;
build(Node[o].l, l, mid);
build(Node[o].r, mid + , r);
} void update(int pre, int &o, int l, int r, int kth) {
o = ++ tot;
Node[o] = Node[pre];
Node[o].size ++;
if(l >= r) return;
int mid = (l + r) >> ;
if(kth <= mid)
update(Node[pre].l, Node[o].l, l, mid, kth);
else
update(Node[pre].r, Node[o].r, mid + , r, kth);
} int query(int r1, int r2, int l, int r, int kth) {
if(l >= r) return l;
int lc = Node[Node[r2].l].size - Node[Node[r1].l].size;
int mid = (l + r) >> ;
if(lc >= kth) {
int ans = query(Node[r1].l, Node[r2].l, l, mid, kth);
return ans;
}
else {
int ans = query(Node[r1].r, Node[r2].r, mid + , r, kth - lc);
return ans;
}
} int Q(int x, int k) {
int l = num[x], r = mx[x];
return a[query(root[l - ], root[r], , n, k)].id;
} int main() {
int u, v, x, k;
scanf("%d", &n);
for(int i = ; i <= n; ++ i) scanf("%d", &w[i]);
for(int i = ; i < n; ++ i) {
scanf("%d%d", &u, &v);
insert(u, v); insert(v, u);
}
dfs();
for(int i = ; i <= n; ++ i) {
a[i].v = w[seg[i]];
a[i].pos = i;
a[i].id = seg[i];
}
sort(a + , a + n + );
for(int i = ; i <= n; ++ i) {
rank[a[i].pos] = i;
}
build(root[], , n);
for(int i = ; i <= n; ++ i) {
update(root[i - ], root[i], , n, rank[i]);
}
scanf("%d", &m);
for(int i = ; i <= m; ++ i) {
scanf("%d%d", &x, &k);
printf("%d\n", Q(x, k));
}
return ;
}
人工栈+可持久化线段树