D - Minimum Steiner Tree

思考一个点作为关键点可能满足的条件：

指定顶点 $V_i$
作为二个指定顶点的必经之路。因为是树，路径唯一，所以舍弃中间点会使得2个顶点无法联通

那么点的类型就分为3类：

指定顶点
非指定但关键
非指定非关键

无论是普通DFS检查还是拓扑序算法删点都可以判断任意点的类型

//拓扑序
const int N = 2e5 + 10;

vector<int> edge[N];

int n, k, d[N];
int q[N];
bool b[N];

void solve(){
    cin >> n >> k;
    for (int i = 1; i < n; i ++ ){
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
        ++ d[x], ++ d[y];
    }
    for (int i = 1; i <= k; i ++ ){
        int v;
        cin >> v;
        b[v] = true;
    }
    int front = 1, rear = 0;
    for (int i = 1; i <= n; i ++ ) 
        if (!b[i] && d[i] == 1) 
            q[++rear] = i;
    while (front <= rear){
        int x = q[front];
        ++ front;
        for (auto y : edge[x])
            if (!b[y] && -- d[y] == 1){
                q[++rear] = y;
            }
    }
    cout << n - rear ;
}

E - Train Delay

从时间排序的角度思考。
对所有的时间排序就能得到大小为 $2m$的数组。
设置 $D[j]$ 为站点 $j$ 的最近到达时间。
时间分为2类

对于出发时间，需要满足 $T_i \geq D[A]$, 那么 $X[i] = max(X[i], D[A] - T_i)$
对于到达时间, $D[i]$ 的取值会因延迟而增大，即 $D[B] = max(D[B], X[i] + T_i)$

因为时间从小到大排序，使得新时间数组没有后效性，所以可以递推解决。

struct Node{
    int A, B, ty, t, pos;
    bool operator<(const Node &A) const{
        if (t == A.t)
            return ty < A.ty; //先到达 后开始
        return t < A.t;
    }
}a[N];

int n, m;
int x[N], D[N];

void solve() {
    cin >> n >> m >> x[1];
    for (int i = 1; i <= m; i ++ ){
        int A, B, s, t; cin >> A >> B >> s >> t;
        a[i] = {A, B, 1, s, i};
        a[i + m] = {A, B, 0, t, i};
    }
    sort(a + 1, a + 2 * m + 1);
    for (int i = 1; i <= 2 * m; i ++ ){
        if (a[i].ty == 1){ //出发事件
            x[a[i].pos] = max(x[a[i].pos], D[a[i].A] - a[i].t);
        }else{//到达事件
            D[a[i].B] = max(D[a[i].B], a[i].t + x[a[i].pos]);
        }
    }
    for (int i = 2; i <= m; i ++ )
        cout << x[i] << ' ';
}

F - Dividing Game

类Nim游戏
每个数 $x$ 可以当作数目为 $cnt$ 的一堆石子
$cnt$ 取值的结论就是 $x$ 分解质因子的指数和

int n;

void solve() {
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        int x, cnt = 0;
        cin >> x;
        for (int j = 2; j <= x / j; j ++ ){
            while (x % j == 0){
                x /= j;
                ++ cnt;
            }
        }
        if (x != 1) ++ cnt;
        res ^= cnt;
    }
    cout << (!res ? "Bruno" : "Anna");
}

G - Add and Multiply Queries

注意到

保证给定类型三查询的答案最多超过 $1e18$，并且 $1e18 \le 2^{64}$

显然每次最优操作是乘 $B_i$ 的总次数不会超过64
只有 $B_i \geq 2$ 时才会考虑乘法，也就是 $[1, n]$最多有64个 $B_i$ 需要考虑，每2个 $B_i$ 之间无脑加即可。
现在问题来到了

找满足条件的 $B_i$
区间求和 $A_i$

找 $B_i$ 可以用Set先存下满足条件的 $B_i$ 的下标,再用内置的二分函数查找。
而区间求和涉及单点修改和区间查询操作，树状数组完全可以胜任。
注意选择乘 $B_i \geq 2$ 不一定最优，记得特判。
总的时间复杂度为max($N$, $M64log64$)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;
typedef long long ll;

const int N = 1e5 + 10;

int n, m;
int A[N], B[N];
ll c[N];

int lowbit(int x) {return x & -x;}

void modify(int x, int pos){
    for (; x <= n; x += lowbit(x)) c[x] += pos;
}

ll query(int x){
    ll res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> A[i];
    for (int i = 1; i <= n; i ++ ) cin >> B[i];

    //build
    for (int i = 1; i <= n; i ++ ) modify(i, A[i]);
    set<int> se;
    for (int i = 1; i <= n; i ++ ) if (B[i] > 1) se.insert(i);

    cin >> m;
    while (m -- ){
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1){
            modify(x, - A[x] + y);
            A[x] = y;
        }else if (op == 2){
            if (B[x] > 1) se.erase(x);
            B[x] = y;
            if (B[x] > 1) se.insert(x);
        }else{
            ll res = A[x++];
            while (x <= y){
                auto it = se.lower_bound(x);
                if (it == se.end() || *it > y){
                    res += query(y) - query(x - 1);
                    break;
                }else{
                    res += query(*it - 1) - query(x - 1);
                    res = max(res + A[*it], res * B[*it]);
                    x = *it + 1;
                }
            }
            cout << res << '\n';
        }
    }
}

signed main() {
    IOS;
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

368ABC题解

D - Minimum Steiner Tree

E - Train Delay

F - Dividing Game

G - Add and Multiply Queries