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 partitioncntChild[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 partitionsfor(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 colorvoid update_node(int v, int delta){// delta = +1 for add red, -1 for remove redfor(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});}// 重心分解build_centroid(1, -1);// initialize totals by adding initial red nodesfor(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){// toggleif(color[v]){// currently red -> removeupdate_node(v, -1);color[v] = 0;} else {update_node(v, +1);color[v] = 1;}} else {// querycout << query_node(v) << '\n';}}return 0;}
投递美团等公司10个岗位