美团笔试0823笔试

A:
可以直接贪心
B.
聚类模拟
C.
考虑0-min(x,y)-max(x,y)-n。第一段考虑因子的交集，第二段考虑max(x,y)因子，和min(x,y)倍数并集，第三段考虑x和y倍数减去最大公约数的倍数（容斥原理）。
D.
按照树重心分治预处理，记录重心分治的递归过程，每个节点最多存在logn个递归的子树中，更新和查询依据存储的递归过程来计算。每个重心存每个分支到它的节点和。这里需要根据重心去重构树
贴个代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, q;
const int MAXN = 200000 + 5;

vector<pair<int,int>> adj[MAXN]; // (to, weight)
int sz[MAXN];
bool removed_[MAXN];
int parent_centroid[MAXN];

void dfs_size(int u, int p){
    sz[u] = 1;
    for(auto [v,w]: adj[u]){
        if(v==p || removed_[v]) continue;
        dfs_size(v,u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int p, int total){
    for(auto [v,w]: adj[u]){
        if(v==p || removed_[v]) continue;
        if(sz[v] > total/2) return find_centroid(v,u,total);
    }
    return u;
}

void collect_nodes(int start,int p, ll dist, vector<pair<int,ll>>& out){
    out.emplace_back(start, dist);
    for(auto [v,w]: adj[start]){
        if(v==p || removed_[v]) continue;
        collect_nodes(v, start, dist + w, out);
    }
}

struct AncInfo { int c; int idx; ll dist; };
vector<AncInfo> anc[MAXN];

ll totCnt[MAXN], totSumDist[MAXN];
vector<ll> cntChild[MAXN], sumChild[MAXN];

void build_centroid(int entry, int p){
    dfs_size(entry, -1);
    int c = find_centroid(entry, -1, sz[entry]);
    removed_[c] = true;
    parent_centroid[c] = p;

    // 重心
    anc[c].push_back({c, -1, 0});

    int childIndex = 0;
    for(auto [v,w]: adj[c]){
        if(removed_[v]) continue;
        vector<pair<int,ll>> nodes;
        collect_nodes(v, c, w, nodes); // distances from node to centroid c
        // make storage for this child partition
        cntChild[c].push_back(0);
        sumChild[c].push_back(0);
        for(auto &pr : nodes){
            int node = pr.first;
            ll d = pr.second;
            anc[node].push_back({c, childIndex, d});
        }
        ++childIndex;
    }

    // recurse on partitions
    for(auto [v,w] : adj[c]){
        if(removed_[v]) continue;
        build_centroid(v, c);
    }
    // do not unmark removed_ -- centroid stays removed in decomposition
}

vector<int> color; // 0/1 current color

void update_node(int v, int delta){
    // delta = +1 for add red, -1 for remove red
    for(auto &a : anc[v]){
        int c = a.c;
        int idx = a.idx;
        ll d = a.dist;
        totCnt[c] += delta;
        totSumDist[c] += delta * d;
        if(idx != -1){
            cntChild[c][idx] += delta;
            sumChild[c][idx] += delta * d;
        }
    }
}

ll query_node(int v){
    ll ans = 0;
    for(auto &a : anc[v]){
        int c = a.c;
        int idx = a.idx;
        ll d = a.dist;
       
        ll contrib = totSumDist[c] + totCnt[c] * d;
        if(idx != -1){
            contrib -= (sumChild[c][idx] + cntChild[c][idx] * d);
        }
        ans += contrib;
    }
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    color.assign(n+1,0);
    for(int i=1;i<=n;i++){
        int ci; cin >> ci; color[i] = ci;
    }
    for(int i=0;i<n-1;i++){
        int u,v,w; cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    // 重心分解#牛客AI配图神器#
    build_centroid(1, -1);

    // initialize totals by adding initial red nodes
    for(int i=1;i<=n;i++){
        if(color[i]) update_node(i, +1);
    }

    // 处理查询
    for(int i=0;i<q;i++){
        int t, v; cin >> t >> v;
        if(t==1){
            // toggle
            if(color[v]){
                // currently red -> remove
                update_node(v, -1);
                color[v] = 0;
            } else {
                update_node(v, +1);
                color[v] = 1;
            }
        } else {
            // query
            cout << query_node(v) << '\n';
        }
    }
    return 0;
}