Codeforces 588E(倍增+归并排序合并链信息)

发表于 | 分类于 | | + s

Codeforces 588E
题意：给一棵树$n$个点，再给$m$个人，$m$个人所在的点同时每个人都有一个编号$i$，
你的任务就是找到$uv$这条路的前$k$个人，输出其编号。

直接倍增，每个倍增记录$i$点到$2^j$个祖先的前10最小的点，然后合并信息即可。
如何合并信息呢？我们让两个数组都为有序的，用归并排序实现$O(20)$合并。

注意卡常题, 代码中标注了卡常的地方

知识点：
链合并这种思想非常方便对于查询。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
    return x * f;
}//1快读 

const int MAXN = 100000 + 10, LOGS = 20;

struct myVec {
    int n, a[30];//2不用vector
    myVec() {n = 0, ms(a, 0);}
    void ins(int x) {a[++n] = x;}
};
myVec merge(myVec &a, myVec &b) {
    myVec ans;
    int u = a.n, v = b.n;
    int i = 1, j = 1;
    while (i <= u && j <= v) {
        if (a.a[i] < b.a[j]) {
            ans.ins(a.a[i]), i++; 
        } else if (a.a[i] > b.a[j]) {
            ans.ins(b.a[j]), j++;
        } else ans.ins(a.a[i]), i++, j++; 
    }
    while (i <= u) {
        if (ans.a[ans.n - 1] == a.a[i]) i++;
        else ans.ins(a.a[i]), i++;
    }
    while (j <= v) {
        if (ans.a[ans.n - 1] == b.a[j]) j++;
        else ans.ins(b.a[j]), j++;
    }//3去重不用unique 
    if (ans.n > 10) ans.n = 10;
    return ans;
}

int n, m, q, dep[MAXN], pre[MAXN][LOGS + 5];
vector<int> G[MAXN];
myVec c[MAXN], tax[MAXN][LOGS + 5];

inline void ins(int x, int y) {G[x].push_back(y), G[y].push_back(x);}

void dfs(int u, int pa) {
    dep[u] = dep[pa] + 1, pre[u][0] = pa, tax[u][0] = merge(c[u], c[pa]);
    for (int i = 1; i <= LOGS; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
    for (int i = 1; i <= LOGS; i++) tax[u][i] = merge(tax[u][i - 1], tax[pre[u][i - 1]][i - 1]);
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (v != pa) dfs(v, u);
    }
}
int LCA(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = LOGS; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
    if (a == b) return a;
    for (int i = LOGS; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
    return pre[a][0];
}
void pro(int u, int v, int a) {
    int lca = LCA(u, v);
    myVec ans = merge(c[u], c[v]);
    ans = merge(ans, c[lca]);
    for (int i = LOGS; i >= 0; i--) if (dep[pre[u][i]] >= dep[lca]) ans = merge(ans, tax[u][i]), u = pre[u][i];
    for (int i = LOGS; i >= 0; i--) if (dep[pre[v][i]] >= dep[lca]) ans = merge(ans, tax[v][i]), v = pre[v][i];
    printf("%d ", min(a, ans.n));
    for (int i = 1; i <= min(a, ans.n); i++) printf("%d ", ans.a[i]);
    puts(""); 
}

void clean() {
    dep[0] = 0;
}
int solve() {
    clean();
    for (int x, y, i = 1; i < n; i++) x = read(), y = read(), ins(x, y);
    for (int gg, i = 1; i <= m; i++) {
        gg = read(); 
        if (c[gg].n != 10) c[gg].ins(i);
    }
    dfs(1, 0);
    for (int i = 1; i <= q; i++) {
        int v = read(), u = read(), a = read();
        pro(v, u, a); 
    }
    return 0; 
}
int main() {
    n = read(), m = read(), q = read(), solve();
    return 0;
}
------ 本文结束 ------