第一题就LCA即可。不过推荐用Tarjan(最快,常数很小)。然后Tarjan的时候顺便就出一个dist[i]，表示i节点到根节点的距离。求出了LCA，那么两点间的距离就为dist[u] + dist[v] - 2 * dist[lca]。
Code
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#ifndef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} typedef class Edge {
public:
int end;
int next;
int w;
Edge(const int end = , const int next = , const int w = ):end(end), next(next), w(w){ }
}Edge; typedef class MapManager{
public:
int ce;
Edge* edges;
int* h;
MapManager():ce(), edges(NULL), h(NULL){ }
MapManager(int points, int limit):ce(){
edges = new Edge[(const int)(limit + )];
h = new int[(const int)(points + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end, int w){
edges[++ce] = Edge(end, h[from], w);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end, int w){
addEdge(from, end, w);
addEdge(end, from, w);
}
Edge& operator [](int pos){
return edges[pos];
}
}MapManager;
#define m_begin(g, i) (g).h[(i)] typedef class union_found{
public:
int *f;
union_found():f(NULL) {}
union_found(int points) {
f = new int[(const int)(points + )];
}
int find(int x) {
if(f[x] != x) return f[x] = find(f[x]);
return f[x];
}
void unit(int fa, int so) {
int ffa = find(fa);
int fso = find(so);
f[fso] = ffa;
}
int& operator [](int pos){
return f[pos];
}
}union_found; int n, m;
MapManager g;
MapManager q;
int *results;
boolean* enable;
int *querya, *queryb;
union_found uf;
boolean* visited;
int* dist; inline void init(){
readInteger(n);
g = MapManager(n, * n);
for(int i = , a, b, c; i < n; i++){
readInteger(a);
readInteger(b);
readInteger(c);
g.addDoubleEdge(a, b, c);
}
readInteger(m);
q = MapManager(n, * m);
querya = new int[(const int)(m + )];
queryb = new int[(const int)(m + )];
results = new int[(const int)(m + )];
enable = new boolean[(const int)(m + )];
dist = new int[(const int)(n + )];
uf = union_found(n);
visited = new boolean[(const int)(n + )];
memset(visited, false, sizeof(boolean) * (n + ));
memset(enable, true, sizeof(boolean) * (m + ));
for(int i = ; i <= m; i++){
readInteger(querya[i]);
readInteger(queryb[i]);
q.addDoubleEdge(querya[i], queryb[i], i);
}
dist[] = ;
} void tarjan(int node, int f){
uf[node] = node;
visited[node] = true;
for(int i = m_begin(g, node); i != ; i = g[i].next){
int& e = g[i].end;
if(e == f) continue;
dist[e] = dist[node] + g[i].w;
tarjan(e, node);
uf[e] = node;
}
for(int i = m_begin(q, node); i != ; i = q[i].next) {
int& e = q[i].end;
if(visited[e] && enable[q[i].w]){
int lca = uf.find(e);
results[q[i].w] = lca;
enable[q[i].w] = false;
}
}
} inline void solve(){
tarjan(, );
for(int i = ; i <= m; i++){
int dis = dist[querya[i]] + dist[queryb[i]] - * dist[results[i]];
printf("%d\n", dis);
}
} int main(){
freopen("distance.in", "r", stdin);
freopen("distance.out", "w", stdout);
init();
solve();
return ;
}
distance (Tarjan)
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#ifndef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} template<typename T>class Matrix{
public:
T *p;
int lines;
int rows;
Matrix():p(NULL){ }
Matrix(int rows, int lines):lines(lines), rows(rows){
p = new T[(lines * rows)];
}
T* operator [](int pos){
return (p + pos * lines);
}
};
#define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows) ///map template starts
typedef class Edge{
public:
int end;
int next;
int w;
Edge(const int end = , const int next = , const int w = ):end(end), next(next), w(w){}
}Edge;
typedef class MapManager{
public:
int ce;
int *h;
int w;
Edge *edge;
MapManager(){}
MapManager(int points, int limit):ce(){
h = new int[(const int)(points + )];
edge = new Edge[(const int)(limit + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end, int w){
edge[++ce] = Edge(end, h[from], w);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end, int w){
addEdge(from, end, w);
addEdge(end, from, w);
}
Edge& operator[] (int pos) {
return edge[pos];
}
}MapManager;
#define m_begin(g, i) (g).h[(i)]
///map template ends int n, m;
int cnt = ;
Matrix<int> st;
int* seq;
int* dep;
int *app;
MapManager g;
int *mlog2;
long long *dist; inline void init() {
readInteger(n);
g = MapManager(n, * n);
seq = new int[(const int)( * n + )];
dist = new long long[(const int)(n + )];
dep = new int[(const int)(n + )];
app = new int[(const int)(n + )];
for(int i = , a, b, w; i < n; i++){
readInteger(a);
readInteger(b);
readInteger(w);
g.addDoubleEdge(a, b, w);
}
dist[] = ;
dep[] = ;
} void dfs(int node, int f) {
seq[++cnt] = node;
app[node] = cnt;
dep[node] = dep[f] + ;
for(int i = m_begin(g, node); i != ; i = g[i].next) {
int& e = g[i].end;
if(e == f) continue;
dist[e] = dist[node] + g[i].w;
dfs(e, node);
seq[++cnt] = node;
}
} inline void init_log() {
mlog2 = new int[(const int)( * n + )];
mlog2[] = ;
for(int i = ; i <= * n; i++)
mlog2[i] = mlog2[i / ] + ;
} inline void init_st() {
init_log();
st = Matrix<int>(cnt, mlog2[cnt] + );
for(int i = ; i <= cnt; i++)
st[i][] = seq[i];
for(int j = ; j <= mlog2[cnt]; j++)
for(int i = ; i + ( << j) - <= cnt; i++)
st[i][j] = (dep[st[i][j - ]] < dep[st[i + ( << (j - ))][j - ]]) ? (st[i][j - ]) : (st[i + ( << (j - ))][j - ]);
} inline int lca(int a, int b) {
if(app[a] > app[b]) swap(a, b);
int pos = mlog2[app[b] - app[a] + ];
int u = st[app[a]][pos];
int v = st[app[b] - ( << pos) + ][pos];
return (dep[u] > dep[v]) ? (v) : (u);
} long long dis;
inline void solve() {
readInteger(m);
for(int i = , a, b; i <= m; i++){
readInteger(a);
readInteger(b);
int l = lca(a, b);
dis = dist[a] + dist[b] - * dist[l];
printf(AUTO"\n", dis);
}
} int main() {
freopen("distance.in", "r", stdin);
freopen("distance.out", "w", stdout);
init();
dfs(, );
init_st();
solve();
return ;
}
distance (st table)
话说ST表在n，q都尽量大的情况下，其他数据随机，竟然平均一个点比Tarjan 0.05s左右。（也有可能是我的st表写得比较丑）
第二题还是一遍dfs序，接着可以开开心心地放线段树去装逼了。(然而我把某些"+="写成了"="，于是AK又没有了。。一定是写这道题和检查的时候头脑都不清醒)
Code
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} typedef class Edge {
public:
int end;
int next;
Edge(const int end = , const int next = ):end(end), next(next){ }
}Edge; typedef class MapManager{
public:
int ce;
Edge* edges;
int* h;
MapManager():ce(), edges(NULL), h(NULL){ }
MapManager(int points, int limit):ce(){
edges = new Edge[(const int)(limit + )];
h = new int[(const int)(points + )];
memset(h, , sizeof(int) * (points + ));
}
inline void addEdge(int from, int end){
edges[++ce] = Edge(end, h[from]);
h[from] = ce;
}
inline void addDoubleEdge(int from, int end){
addEdge(from, end);
addEdge(end, from);
}
Edge& operator [](int pos){
return edges[pos];
}
}MapManager;
#define m_begin(g, i) (g).h[(i)] typedef class SegTreeNode{
public:
long long sum;
int l, r;
SegTreeNode *left, *right;
long long lazy;
SegTreeNode(int l, int r):l(l), r(r), sum(), lazy(), left(NULL), right(NULL){ } inline void pushUp(){
this->sum = left->sum + right->sum;
} inline void pushDown(){
left->lazy += lazy;
right->lazy += lazy;
left->sum += lazy * (left->r - left->l + );
right->sum += lazy * (right->r - right->l + );
lazy = ;
}
}SegTreeNode; typedef class SegTree {
public:
SegTreeNode* root;
SegTree():root(NULL){ }
SegTree(int size) {
build(root, , size);
} void build(SegTreeNode*& node, int l, int r){
node = new SegTreeNode(l, r);
if(l == r) return;
int mid = (l + r) >> ;
build(node->left, l, mid);
build(node->right, mid + , r);
} void update(SegTreeNode*& node, int l, int r, int from, int end, long long val){
if(l == from && r == end){
node->sum += val * (r - l + );
node->lazy += val;
return;
}
if(node->lazy) node->pushDown();
int mid = (l + r) >> ;
if(end <= mid) update(node->left, l, mid, from, end, val);
else if(from > mid) update(node->right, mid + , r, from, end, val);
else{
update(node->left, l, mid, from, mid, val);
update(node->right, mid + , r, mid + , end, val);
}
node->pushUp();
} long long query(SegTreeNode*& node, int index){
if(node->l == index && node->r == index){
return node->sum;
}
if(node->lazy) node->pushDown();
int mid = (node->l + node->r) >> ;
if(index <= mid) return query(node->left, index);
return query(node->right, index);
} long long query(SegTreeNode*& node, int from, int end){
if(node->l == from && node->r == end){
return node->sum;
}
if(node->lazy) node->pushDown();
int mid = (node->l + node->r) >> ;
if(end <= mid) return query(node->left, from, end);
if(from > mid) return query(node->right, from, end);
return query(node->left, from, mid) + query(node->right, mid + , end);
}
}SegTree; int n, m;
SegTree st;
int cnt = ;
int* visitID;
int* exitID;
MapManager g; inline void init() {
readInteger(n);
g = MapManager(n, * n);
for(int i = , a, b; i < n; i++){
readInteger(a);
readInteger(b);
g.addDoubleEdge(a, b);
}
visitID = new int[(const int)(n + )];
exitID = new int[(const int)(n + )];
} void dfs(int node, int last){
visitID[node] = ++cnt;
for(int i = m_begin(g, node); i != ; i = g[i].next) {
int& e = g[i].end;
if(e == last) continue;
dfs(e, node);
}
exitID[node] = cnt;
} inline void solve() {
dfs(, );
readInteger(m);
st = SegTree(n);
char cmd[];
int a, b;
while(m--) {
scanf("%s", cmd);
readInteger(a);
if(cmd[] == 'g') {
readInteger(b);
st.update(st.root, , n, visitID[a], exitID[a], b);
}else if(cmd[] == 's'){
long long res = st.query(st.root, visitID[a]);
printf(AUTO"\n", res);
}else if(cmd[] == 'a'){
long long res = st.query(st.root, visitID[a], exitID[a]);
printf(AUTO"\n", res);
}
}
} int main() {
freopen("redpacket.in", "r", stdin);
freopen("redpacket.out", "w", stdout);
init();
solve();
return ;
}
一看就发现是专为值域线段树设置的裸题。
Code
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#ifndef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} typedef class SegTreeNode {
public:
int s;
SegTreeNode* left, *right; inline void pushUp(){
s = left->s + right->s;
}
}SegTreeNode; typedef class SegTree {
public:
int lb, rb;
SegTreeNode* root;
SegTree():root(NULL) { }
SegTree(int lb, int rb, int* list):lb(lb), rb(rb){
build(root, , rb - lb + , list);
} void build(SegTreeNode*& node, int l, int r, int* list){
node = new SegTreeNode();
if(l == r){
node->s = list[l];
return;
}
int mid = (l + r) >> ;
build(node->left, l, mid, list);
build(node->right, mid + , r, list);
node->pushUp();
} void update(SegTreeNode*& node, int l, int r, int index, int val){
if(l == index && r == index){
node->s += val;
smax(node->s, );
return;
}
int mid = (l + r) >> ;
if(index <= mid) update(node->left, l, mid, index, val);
else update(node->right, mid + , r, index, val);
node->pushUp();
} int findKth(SegTreeNode*& node, int l, int r, int k){
if(l == r) return l + lb - ;
int ls = node->left->s;
int mid = (l + r) >> ;
if(k <= ls) return findKth(node->left, l, mid, k);
return findKth(node->right, mid + , r, k - ls);
}
}SegTree; int n;
int lb, rb;
int* list;
SegTree st;
inline void init() {
readInteger(lb);
readInteger(rb);
list = new int[(const int)(rb - lb + )];
for(int i = lb; i <= rb; i++){
readInteger(list[i - lb + ]);
}
st = SegTree(lb, rb, list);
} inline void solve() {
const int L = rb - lb + ;
readInteger(n);
char cmd[];
int a;
while(n--) {
scanf("%s", cmd);
readInteger(a);
if(cmd[] == 'a'){
st.update(st.root, , L, a - lb + , );
}else if(cmd[] == 'd'){
st.update(st.root, , L, a - lb + , -);
}else{
int res = st.findKth(st.root, , L, a);
printf("%d\n", res);
}
}
} int main(){
freopen("kth.in", "r", stdin);
freopen("kth.out", "w", stdout);
init();
solve();
return ;
}
值域线段树
然后我还用了替罪羊树(然而发现，都快成普通的二叉搜索树了)，O(n)离线建完整棵树，插入删除都不需要重构，即使为count为0也不管(删掉它需要花费更过的时间)。不过测了后发现，略微比值域线段树快一点，应该是因为各种操作在中途完成就开始返回了。
Code
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<algorithm>
#ifndef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
aFlag = -;
x = getchar();
}
for(u = x - ''; isdigit((x = getchar())); u = u * + x - '');
ungetc(x, stdin);
u *= aFlag;
} template<typename T>
class ScapegoatTreeNode {
public:
T val;
int count;
int size;
ScapegoatTreeNode* next[];
ScapegoatTreeNode():count(), size(){
memset(next, , sizeof(next));
}
ScapegoatTreeNode(T val):val(val), count(), size(){
memset(next, , sizeof(next));
} inline void maintain() {
size = count;
for(int i = ; i < ; i++)
if(next[i] != NULL)
size += next[i]->size;
} inline void addCount(int c){
if(count == && c < ) return;
size += c, count += c;
} inline int cmp(T x){
if(val == x) return -;
return (x < val) ? () : ();
}
}; template<typename T>
class ScapegoatTree {
protected:
static void insert(ScapegoatTreeNode<T>*& node, T val){
if(node == NULL){
node = new ScapegoatTreeNode<T>(val);
return;
}
int d = node->cmp(val);
if(d == -){
node->addCount();
return;
}
insert(node->next[d], val);
node->maintain();
} static boolean remove(ScapegoatTreeNode<T>*& node, T val){
if(node == NULL) return false;
int d = node->cmp(val);
if(d == -){
node->addCount(-);
return true;
}
boolean res = remove(node->next[d], val);
if(res) node->maintain();
return res;
} static ScapegoatTreeNode<T>* findKth(ScapegoatTreeNode<T>*& node, int k){
int ls = (node->next[] == NULL) ? () : (node->next[]->size);
if(k >= ls + && k <= ls + node->count) return node;
if(k <= ls) return findKth(node->next[], k);
return findKth(node->next[], k - ls - node->count);
}
public:
ScapegoatTreeNode<T>* root;
vector<ScapegoatTreeNode<T>*> lis; ScapegoatTree():root(NULL){ } ScapegoatTreeNode<T>* rebuild(int l, int r){
if(l > r) return NULL;
int mid = (l + r) >> ;
ScapegoatTreeNode<T>*& node = lis[mid];
node->next[] = rebuild(l, mid - );
node->next[] = rebuild(mid + , r);
node->maintain();
return node;
} void rebuild(ScapegoatTreeNode<T>*& node, ScapegoatTreeNode<T>*& f){
lis.clear();
travel(node);
int d = -;
if(f != NULL) d = f->cmp(node->val);
ScapegoatTreeNode<T>* res = rebuild(, lis.size() - );
if(d != -) f->next[d] = res;
else root = res;
} void insert(T val){
insert(root, val);
} void remove(T val){
remove(root, val);
} ScapegoatTreeNode<T>* findKth(int k){
return findKth(root, k);
}
}; int n;
int lb, rb;
ScapegoatTree<int> s; inline void init() {
readInteger(lb);
readInteger(rb);
for(int i = lb; i <= rb; i++){
ScapegoatTreeNode<int>* node = new ScapegoatTreeNode<int>(i);
readInteger(node->count);
node->maintain();
s.lis.push_back(node);
}
s.root = s.rebuild(, s.lis.size() - );
} inline void solve() {
readInteger(n);
char cmd[];
int a;
while(n--) {
scanf("%s", cmd);
readInteger(a);
if(cmd[] == 'a'){
s.insert(a);
}else if(cmd[] == 'd'){
s.remove(a);
}else{
ScapegoatTreeNode<int>* node = s.findKth(a);
printf("%d\n", node->val);
}
}
} int main(){
freopen("kth.in", "r", stdin);
freopen("kth.out", "w", stdout);
init();
solve();
return ;
}
替罪羊树