https://cn.vjudge.net/problem/SPOJ-COT
插上 大佬的代码 和 我的。。。以后再看吧。。。
Count on a tree
大佬：http://www.cnblogs.com/Sunnie69/p/5511684.html
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std; const int maxn=+;
int n,m,cnt,num;
int a[maxn],id[maxn],b[maxn],head[maxn],p[maxn],f[maxn],root[maxn];
bool vis[maxn];
struct edge{
int to,next;
edge(){}
edge(int a,int b):to(a),next(b){}
}g[maxn<<];
struct Qry{
int u,v,k,lca;
Qry(){}
Qry(int a,int b,int c,int d):u(a),v(b),k(c),lca(d){}
}Q[maxn];
struct node{ int l,r,s; }t[maxn*];
struct qry{
int v,id;
qry(){}
qry(int a,int b):v(a),id(b){}
};
vector <qry> q[maxn]; inline int find(int x){ return x==f[x]?x:f[x]=find(f[x]); }
void add_edge(int u,int v){
g[++cnt]=edge(v,head[u]); head[u]=cnt;
g[++cnt]=edge(u,head[v]); head[v]=cnt;
}
void update(int l,int r,int &pos,int d){
t[++num]=t[pos]; pos=num; t[pos].s++;
if(l==r) return;
int mid=l+(r-l)/;
if(d<=mid) update(l,mid,t[pos].l,d);
else update(mid+,r,t[pos].r,d);
}
bool cmp(int x,int y){ return a[x]<a[y]; }
void dfs(int u){
f[u]=u; root[u]=root[p[u]]; update(,n,root[u],b[u]);
for(int i=head[u];i;i=g[i].next){
if(g[i].to!=p[u]){
p[g[i].to]=u;
dfs(g[i].to);
f[g[i].to]=u;
}
}
vis[u]=true;
int size=q[u].size();
for(int i=;i<size;i++) if(vis[q[u][i].v]) Q[q[u][i].id].lca=find(q[u][i].v);
}
void init(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]), id[i]=i;
sort(id+,id+n+,cmp);
for(int i=;i<=n;i++) b[id[i]]=i;
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
}
for(int i=;i<=m;i++){
scanf("%d%d%d",&Q[i].u,&Q[i].v,&Q[i].k);
q[Q[i].u].push_back(qry(Q[i].v,i)); q[Q[i].v].push_back(qry(Q[i].u,i));
}
}
int query(int l,int r,int x,int y,int ra,int a,int k){
if(l==r) return l;
int mid=l+(r-l)/;
int s=t[t[x].l].s+t[t[y].l].s-*t[t[ra].l].s;
if(b[a]>=l&&b[a]<=mid) s++;
if(k<=s) return query(l,mid,t[x].l,t[y].l,t[ra].l,a,k);
else return query(mid+,r,t[x].r,t[y].r,t[ra].r,a,k-s);
}
void solve(){
dfs();
for(int i=;i<=m;i++){
if(Q[i].u==Q[i].v){ printf("%d\n",a[Q[i].u]); continue; }
printf("%d\n",a[id[query(,n,root[Q[i].u],root[Q[i].v],root[Q[i].lca],Q[i].lca,Q[i].k)]]);
}
}
int main(){
init();
solve();
return ;
}
蒟蒻：
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(a, n) for(int i=a; i<=n; i++)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int n, m, x, y, k, cnt;
int root[maxn], a[maxn], f[maxn], head[maxn], vis[maxn], pre[maxn];
struct node {int l, r, sum;}T[maxn];
struct edge {int v, next, lca;}Edge[maxn];
vector<int> v;
int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + ;}
vector<int> G[maxn]; struct quer {int u, v, id, lca, k;}Q[maxn];
vector<quer> q[maxn];
void add_(int u, int v)
{
Edge[cnt].v = v;
Edge[cnt].next = head[u];
head[u] = cnt++;
}
void add(int u, int v)
{
add_(u, v);
add_(v, u);
} int find(int x)
{
return f[x] == x?x:(f[x] == find(f[x]));
} void update(int l, int r, int& pos, int d)
{
T[++cnt] = T[pos], T[cnt].sum++, pos = cnt;
if(l == r) return;
int mid = l + (r - l) / ;
if(mid >= d) update(l, mid, T[pos].l, d);
else update(mid+, r, T[pos].r, d);
} void lca(int u)
{
f[u] = u;
root[u] = root[pre[u]];
update(, n, root[u], getid(u));
for(int i=head[u]; i!=-; i=Edge[i].next)
{
int v = Edge[i].v;
if(v == pre[u]) continue;
pre[v] = u;
lca(v);
f[v] = u;
}
vis[u] = true;
int size = q[u].size();
rap(, size-)
{
if(vis[q[u][i].v])
{
Q[q[u][i].id].lca = find(q[u][i].v);
}
}
} int query(int l, int r, int x, int y, int ra, int lca, int k)
{
if(l == r) return l;
int mid = l + (r - l) / ;
int sum = T[T[y].l].sum + T[T[x].l].sum - *T[T[ra].l].sum;
int lca_id = getid(lca);
if(lca_id >= l && lca_id <= mid) sum++;
if(sum >= k) return query(l, mid, T[x].l, T[y].l, T[ra].l, lca, k);
else return query(mid+, r, T[x].r, T[y].r, T[ra].r, lca, k - sum);
} int main()
{
mem(head, -);
cnt = ;
scanf("%d%d", &n, &m);
rap(, n)
{
scanf("%d", &a[i]);
v.push_back(a[i]);
}
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
rap(, n-)
{
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
}
rap(, m)
{
scanf("%d%d%d", &Q[i].u, &Q[i].v, &Q[i].k);
Q[i].id = i;
q[Q[i].u].push_back(Q[i]);
q[Q[i].v].push_back(Q[i]);
}
lca();
rap(, m)
{
if(Q[i].u == Q[i].v)
{
printf("%d\n",a[Q[i].u]);
continue;
} printf("%d\n",v[query(, n, root[Q[i].u], root[Q[i].v], root[Q[i].lca], Q[i].lca, Q[i].k) - ]);
}
return ;
}