NC545 扩散

题目描述

给你一个树，初始每个点的权值都是0，有$mm$次操作，每次操作选一个点，把这个点和跟它相邻的点权值都加1，问最后每个点的权值是多少？

1. 直接模拟

直接根据题意模拟，每次操作遍历这个点和它的出边，统计答案。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param q int整型vector 
     * @return int整型vector
     */
    static const int N = 1e5 + 5;
    
    struct Edge {
        int to, next;
    } e[N << 1];

    int head[N], idx = 1;

    void add_edge(int u, int v) {
        e[idx].to = v;
        e[idx].next = head[u];
        head[u] = idx++;
    }
    void clear_graph() {
        memset(head, -1, sizeof(head));
        memset(e, 0, sizeof(e));
        idx = 1;
    }

    
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) {
        vector<int> res(n);
        
        clear_graph();
        
        for (int i = 0; i < n-1; i++) {
            add_edge(u[i], v[i]);
            add_edge(v[i], u[i]);
        }
        
        for (int i = 0; i < m; i++) {
            int id = q[i];
            
            res[id-1]++; // 下标修正
            
            // 对每个边增加
            for (int j = head[id]; ~j; j = e[j].next) {
                int k = e[j].to;
                res[k-1]++;
            }
        }
        
        return res;
    }
};

• 时间复杂度： 最坏是$O(mn)O(mn)$, $mm$次操作，最坏情况是个菊花图，每次都操作根节点，第二重循环复杂度为$O(n)O(n)$, 总计为$O(mn)O(mn)$
• 空间复杂度：$O(n)O(n)$, 前向星存图。

2. 分别统计贡献

权值分为两种情况，分别是自己被操作，和被相邻的点带动操作，我们分别用两个数组统计这两种情况的贡献即可。

统计情况1时，遍历每个操作，对这个点权值+1。

统计情况2时，遍历每个边，看这个边的两个端点$(u,v)(u,\; v)$被操作了几次，则另一个点也被“带动”了对应的次数。

如图所示，先算每次操作对“点本身”的贡献，再遍历边。

以（1,3）边为例：

• 1进行了一次操作，对3的权值贡献1；
• 3进行了一次操作，对1的权值贡献1；

最终统计1的权值为1+1=2（分别来自两种情况）；2的权值为0+3=3，……

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param u int整型vector 
     * @param v int整型vector 
     * @param q int整型vector 
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& q) {
        vector<int> res(n);
        
        vector<int> a(n+1), b(n+1);
        
        for (auto i : q)
            a[i]++;
        
        for (int i = 0; i < n-1; i++)
            b[u[i]] += a[v[i]], b[v[i]] += a[u[i]];
        
        for (int i = 0; i < n; i++)
            res[i] = b[i+1] + a[i+1];
        return res;
    }
};

• 时间复杂度： $O(m+n)O(m+n)$, 一次对$qq$数组的遍历，一次对边的遍历，一次累加
• 空间复杂度：$O(n)O(n)$, 定义了长为$nn$的数组a和b