1 条题解

  • 0
    @ 2025-11-5 21:00:36
    #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;
    }
    
    • 1

    信息

    ID
    471
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    2
    已通过
    1
    上传者