“蔚来杯“2022牛客暑期多校训练营3 ACFHJ

A.Ancestor LCA+暴力查询 题目分析

给出两棵编号 1 − n 1-n 1−n的树 A , B A,B A,B， A , B A,B A,B树上每个节点均有一个权值，给出 k k k个关键点的编号 x 1 … x n x_1…x_n x1​…xn​，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树 A A A上 L C A LCA LCA的权值大于树 B B B上 L C A LCA LCA的权值。

处理出所有关键节点的前缀 L C A LCA LCA和后缀 L C A LCA LCA，然后枚举所有的关键节点求 L C A LCA LCA后 C h e c k Check Check计数即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 862118861;

int a[N], b[N], key[N];
vector g1[N], g2[N];

struct LCA{
    struct edge{ int to, len, next; } E[N];
    int cnt, last[N], fa[N], top[N], deep[N], siz[N], son[N], val[N];
    void addedge(int a, int b, int len = 0){
        E[++cnt] = (edge){b, len, last[a]}, last[a] = cnt;
    }
    void dfs1(int x){
        deep[x] = deep[fa[x]] + 1;
        siz[x] = 1;
        for (int i = last[x]; i; i = E[i].next){
            int to = E[i].to;
            if (fa[x] != to && !fa[to]){
                val[to] = E[i].len;
                fa[to] = x;
                dfs1(to);
                siz[x] += siz[to];
                if (siz[son[x]]  deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]]);
        return deep[x] > n >> k;
    for(int i = 1; i > key[i];
    for(int i = 1; i > a[i];
    for(int i = 2; i > fa;
        ta.addedge(fa, i), ta.addedge(i, fa);
    }
    for(int i = 1; i > b[i];
    for(int i = 2; i > fa;
        tb.addedge(fa, i), tb.addedge(i, fa);
    }
    ta.init(1), tb.init(1);
    pa[1] = pb[1] = key[1], sa[k] = sb[k] = key[k];
    for(int i = 2; i = 1; i--)
        sa[i] = ta.query(sa[i + 1], key[i]), sb[i] = tb.query(sb[i + 1], key[i]);
    int ans = 0;
    for(int i = 1; i  b[qb]) ans++;
    }
    cout