题目：

「力扣挑战赛」有 n 个比赛场馆（场馆编号从 0 开始），场馆之间的通道分布情况记录于二维数组 edges 中，edges[i]= [x, y] 表示第 i 条通道连接场馆 x 和场馆 y(即两个场馆相邻)。初始每个场馆中都有一定人数的志愿者（不同场馆人数可能不同），后续 m 天每天均会根据赛事热度进行志愿者人数调配。调配方案分为如下三种：

将编号为 idx 的场馆内的志愿者人数减半；
将编号为 idx 的场馆相邻的场馆的志愿者人数都加上编号为 idx 的场馆的志愿者人数；
将编号为 idx 的场馆相邻的场馆的志愿者人数都减去编号为 idx 的场馆的志愿者人数。
所有的调配信息记录于数组 plans 中，plans[i] = [num,idx] 表示第 i 天对编号 idx 的场馆执行了第 num 种调配方案。
在比赛结束后对调配方案进行复盘时，不慎将第 0 个场馆的最终志愿者人数丢失，只保留了初始所有场馆的志愿者总人数 totalNum ，以及记录了第 1 ~ n-1 个场馆的最终志愿者人数的一维数组 finalCnt。请你根据现有的信息求出初始每个场馆的志愿者人数，并按场馆编号顺序返回志愿者人数列表。

注意：

测试数据保证当某场馆进行第一种调配时，该场馆的志愿者人数一定为偶数；
测试数据保证当某场馆进行第三种调配时，该场馆的相邻场馆志愿者人数不为负数；
测试数据保证比赛开始时每个场馆的志愿者人数都不超过 10^9；
测试数据保证给定的场馆间的道路分布情况中不会出现自环、重边的情况。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/05ZEDJ

思路：?

拿到这种题，一定一定要先把题读懂，然后再去做，下面我来说一下这道题的思路。

1.我们如果把它当做一道数学题来做，那一定会用解方程的方法，设场馆0最终的人数为x，然后反推到初始状态的数据，最后所有场馆求和解方程。

2.反推思路：从后往前取plans

方案1：操作场馆*2；

方案2：操作场馆相邻场馆减去操作场馆；

方案3：操作场馆相邻场馆加上操作场馆；

3.方程表示：我们这道题使用两个数组表示（长度都为场馆数量）。result[]表示常数项，flag[]表示x前的参数。

所以我们最终场馆的数据为：result[0]=0，因为result[0]我们设为x。

而参数数组：result[0]=1，其他都为0。

4.最后我们只需要用初始总数减去所有常数项，再除参数项的和即可求出x。让对result[]加上参数和x的乘积即可。

注意：?

我在做题过程中遇到的两个bug：

1.我们要主要到志愿者总数totalNum为long类型。这说明数据会非常大，因此我们如果要先求出常数和再做差的话，要把常数和设为long类型，不然会出错。其实参数和我们都应该设为long类型（这是我在写这篇文档时发现的，这里就不修改了）。如果设为int类型，当数据足够大，就会出错。

2.还有一点就是我一开始存储edges时想到了图数据结构，用二维数组存储，这样的话会开辟很大的空间，而竞赛的测试集中必然有超大的数据，这时候二维数组一平方就超出存储容量了。因此这里采用了HashMap<Integer,ArrayList>存储。如果用链表的话，虽然对一条链的遍历很方便，但找到这条链的头结点缺很难。综合来讲，还是HashMap好用。

代码：?

package LiKouQiuJiZhanDuiSai;

import java.util.*;

public class Third {
    public static void main(String[] args) {
        Solution_3 solution3=new Solution_3();
        int [] finalCnt ={7,3};
        int totalNum = 20;
        int[][] edges = {{0,1},{1,2},{0,2}};
        int[][] plans = {{1,0},{1,2},{2,0},{1,2},{3,2}};
        System.out.println(Arrays.toString(solution3.volunteerDeployment(finalCnt,totalNum,edges,plans)));
    }
}
class Solution_3 {
    public int[] volunteerDeployment(int[] finalCnt, long totalNum, int[][] edges, int[][] plans) {
        int[] result=new int[finalCnt.length+1];
        int[] flag=new int[result.length];
        flag[0]=1;
        for(int i=1;i<result.length;i++){
            result[i]=finalCnt[i-1];
        }
        Map<Integer, ArrayList<Integer>> dealEdges=new HashMap<>();
        for(int i=0;i<edges.length;i++){
            //思考
            List<Integer> list=dealEdges.getOrDefault(edges[i][0],new ArrayList<>());
            List<Integer> list1=dealEdges.getOrDefault(edges[i][1],new ArrayList<>());
            list.add(edges[i][1]);
            dealEdges.put(edges[i][0], (ArrayList<Integer>) list);
            list1.add(edges[i][0]);
            dealEdges.put(edges[i][1], (ArrayList<Integer>) list1);
        }
/*        for(int i=0;i<result.length;i++){
            System.out.println(dealEdges.getOrDefault(i,new ArrayList<>()).toString());
        }*/
/*        boolean[][] dealEdges=new boolean[result.length][result.length];
        for(int i=0;i<edges.length;i++){
            dealEdges[edges[i][0]][edges[i][1]]=true;
            dealEdges[edges[i][1]][edges[i][0]]=true;
        }*/
/*        System.out.println(Arrays.toString(result));
        System.out.println(Arrays.toString(flag));
        for(boolean[] b:dealEdges){
            System.out.println(Arrays.toString(b));
        }*/
        for(int i=plans.length-1;i>=0;i--){
            if(plans[i][0]==1){
                result[plans[i][1]]*=2;
                flag[plans[i][1]]*=2;
            }else if(plans[i][0]==2){
                for(int temp:dealEdges.getOrDefault(plans[i][1],new ArrayList<>())){
                    result[temp]-=result[plans[i][1]];
                    flag[temp]-=flag[plans[i][1]];
                }
/*                for(int j=0;j<result.length;j++){
                    if(dealEdges[plans[i][1]][j]){
                        result[j]-=result[plans[i][1]];
                        flag[j]-=flag[plans[i][1]];
                    }
                }*/
            }else if(plans[i][0]==3){
                for(int temp:dealEdges.getOrDefault(plans[i][1],new ArrayList<>())){
                    result[temp]+=result[plans[i][1]];
                    flag[temp]+=flag[plans[i][1]];
                }
            }
        }
        //System.out.println(Arrays.toString(result));
        //System.out.println(Arrays.toString(flag));
        int sumFlag=0;
        for(int i=0;i<flag.length;i++){
            sumFlag+=flag[i];
            totalNum-=result[i];
        }
        //System.out.println(sumFlag+"  "+sum);
        int n=(int) (totalNum/sumFlag);
        for(int i=0;i<result.length;i++){
            result[i]=result[i]+n*flag[i];
        }
        //System.out.println(Arrays.toString(result));
        return result;
    }
}