1 条题解
-
0
#include <bits/stdc++.h> using namespace std; #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define int long long typedef vector<vector<int>> mat; using pii = pair<int, int>; using pdd = pair<double,double>; using u64 = unsigned long long; constexpr int Nn = 2e5 + 10; const int INF = 4e18; struct LCA { int n, K; // 带权邻接表 vector<vector<pair<int,int>>> edge; // {to, w} vector<vector<int>> f; // f[v][k] = v 的 2^k 祖先 vector<int> depth; // 深度 = 层数(边数),仍然是"按边计数" vector<long long> dist; // 从 root 到 v 的加权距离前缀和 LCA(int n_=0): n(n_) { K = 1; while ((1<<K) <= n) ++K; // 2^K > n edge.assign(n+1, {}); f.assign(n+1, vector<int>(K, 0)); // 列 0..K-1 depth.assign(n+1, INT_MAX); dist.assign(n+1, 0); } void addEdge(int u,int v,int w){ edge[u].push_back({v,w}); edge[v].push_back({u,w}); } // 定根 + 预处理:BFS/DFS 都可以,这里 BFS void init(int root){ queue<int> q; fill(depth.begin(), depth.end(), INT_MAX); depth[0] = 0; depth[root] = 1; // 你原来用 1 开始,这里保持一致 dist[root] = 0; // 根到根的距离为 0 f[root][0] = 0; q.push(root); while(!q.empty()){ int u = q.front(); q.pop(); for (auto [v, w] : edge[u]){ if (depth[v] > depth[u] + 1){ depth[v] = depth[u] + 1; // 注意:这里的 depth 仍是"层数",不是权重 f[v][0] = u; dist[v] = dist[u] + w; // 加权前缀和 for (int k = 1; k < K; ++k){ f[v][k] = f[ f[v][k-1] ][k-1]; } q.push(v); } } } } // 提升 a 到与 b 同深(按层数),再同步跳 int lca(int a, int b) const { if (depth[a] < depth[b]) swap(a, b); int diff = depth[a] - depth[b]; for (int i = 0; i < K; ++i) if (diff & (1<<i)) a = f[a][i]; if (a == b) return a; for (int i = K-1; i >= 0; --i){ if (f[a][i] != f[b][i]){ a = f[a][i]; b = f[b][i]; } } return f[a][0]; } // 可选:两点加权距离 long long dist_between(int u, int v) const { int w = lca(u, v); return dist[u] + dist[v] - 2LL * dist[w]; } // 可选:上跳 d 层(按边数) int lift(int v, int d) const { for (int i = 0; i < K; ++i) if (d & (1<<i)) v = f[v][i]; return v; } }; signed main() { IOS; int n,m; cin>>n>>m; LCA tree(n); vector<long long>d1(n+10,0),d2(n+10,0); for(int i=1;i<n;i++){ int u,v; cin>>u>>v; //u--,v--; tree.addEdge(u,v,1); } tree.init(1); while(m--){ int op,u,v,x; cin>>op; if(op==1){ cin>>u>>x; //u--; d1[u]+=x; //cout<<d1[u]<<' '; } else{ cin>>u>>v>>x; //u--,v--; d2[u]+=x; d2[v]+=x; auto p =tree.lca(u,v); d2[p]-=x; if(tree.f[p][0]!=0){ d2[tree.f[p][0]]-=x; } } } auto dfs=[&](auto &&self,int u,int p)->void{ for(auto [v,w] : tree.edge[u]){ if(v==p)continue; d1[v]+=d1[u]; self(self,v,u); d2[u]+=d2[v]; } }; dfs(dfs,1,0); for(int i=1;i<=n;i++)cout<<d1[i]+d2[i]<<' '; cout<<endl; return 0; }
信息
- ID
- 471
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者