Repository navigation
Expand file tree
/
Copy path_5_bonus_2.java
More file actions
184 lines (170 loc) · 17.3 KB
/
Copy path_5_bonus_2.java
File metadata and controls
184 lines (170 loc) · 17.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
package pp.arithmetic.LCP;
import pp.arithmetic.Util;
import java.util.ArrayList;
import java.util.List;
/**
* Created by wangpeng on 2019-10-11.
* <p>
* 力扣决定给一个刷题团队发LeetCoin作为奖励。同时，为了监控给大家发了多少LeetCoin，力扣有时候也会进行查询。
* <p>
*
* <p>
* 该刷题团队的管理模式可以用一棵树表示：
* <p>
* 团队只有一个负责人，编号为1。除了该负责人外，每个人有且仅有一个领导（负责人没有领导）；
* 不存在循环管理的情况，如A管理B，B管理C，C管理A。
*
* <p>
* 力扣想进行的操作有以下三种：
* <p>
* 给团队的一个成员（也可以是负责人）发一定数量的LeetCoin；
* 给团队的一个成员（也可以是负责人），以及他/她管理的所有人（即他/她的下属、他/她下属的下属，……），发一定数量的LeetCoin；
* 查询某一个成员（也可以是负责人），以及他/她管理的所有人被发到的LeetCoin之和。
*
* <p>
* 输入：
* <p>
* N表示团队成员的个数（编号为1～N，负责人为1）；
* leadership是大小为(N - 1) * 2的二维数组，其中每个元素[a, b]代表b是a的下属；
* operations是一个长度为Q的二维数组，代表以时间排序的操作，格式如下：
* operations[i][0] = 1: 代表第一种操作，operations[i][1]代表成员的编号，operations[i][2]代表LeetCoin的数量；
* operations[i][0] = 2: 代表第二种操作，operations[i][1]代表成员的编号，operations[i][2]代表LeetCoin的数量；
* operations[i][0] = 3: 代表第三种操作，operations[i][1]代表成员的编号；
* 输出：
* <p>
* 返回一个数组，数组里是每次查询的返回值（发LeetCoin的操作不需要任何返回值）。由于发的LeetCoin很多，请把每次查询的结果模1e9+7 (1000000007)。
* <p>
*
* <p>
* 示例 1：
* <p>
* 输入：N = 6, leadership = [[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]], operations = [[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]
* 输出：[650, 665]
* 解释：团队的管理关系见下图。
* 第一次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 0;
* 第二次查询时，每个成员得到的LeetCoin的数量分别为（按编号顺序）：500, 50, 50, 0, 50, 15.
* <p>
* <p>
* <image src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/09/09/coin_example_1.jpg" />
* <p>
* 限制：
* <p>
* 1 <= N <= 50000
* 1 <= Q <= 50000
* operations[i][0] != 3 时，1 <= operations[i][2] <= 5000
* <p>
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/coin-bonus
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class _5_bonus_2 {
public static void main(String[] args) {
_5_bonus_2 bonus = new _5_bonus_2();
Util.printArray(bonus.bonus(6, new int[][]{{1, 2}, {1, 6}, {2, 3}, {2, 5}, {1, 4}}, new int[][]{{1, 1, 500}, {2, 2, 50}, {3, 1}, {2, 6, 15}, {3, 1}}));
int[][] l = new int[][]{{1, 283}, {1, 52}, {1, 273}, {1, 217}, {1, 136}, {1, 211}, {1, 179}, {283, 293}, {283, 292}, {283, 227}, {283, 54}, {283, 404}, {283, 378}, {283, 243}, {283, 270}, {283, 46}, {283, 300}, {52, 376}, {52, 267}, {52, 71}, {52, 406}, {273, 9}, {273, 148}, {273, 51}, {273, 102}, {217, 110}, {217, 370}, {217, 125}, {217, 357}, {136, 360}, {136, 260}, {136, 196}, {136, 228}, {136, 103}, {136, 347}, {136, 384}, {211, 25}, {179, 3}, {179, 140}, {179, 56}, {179, 263}, {179, 231}, {293, 326}, {293, 121}, {293, 116}, {293, 21}, {293, 262}, {293, 369}, {293, 183}, {292, 75}, {292, 303}, {292, 330}, {227, 397}, {227, 35}, {227, 279}, {227, 345}, {227, 139}, {227, 391}, {227, 266}, {54, 16}, {404, 214}, {404, 184}, {404, 68}, {404, 27}, {378, 192}, {378, 87}, {378, 39}, {378, 386}, {378, 259}, {243, 94}, {243, 112}, {243, 99}, {243, 182}, {243, 29}, {243, 197}, {270, 23}, {270, 181}, {270, 297}, {46, 351}, {46, 362}, {46, 22}, {46, 61}, {300, 408}, {376, 332}, {267, 349}, {267, 80}, {267, 367}, {267, 226}, {71, 72}, {71, 389}, {71, 163}, {71, 100}, {71, 107}, {71, 92}, {71, 85}, {406, 353}, {406, 199}, {406, 257}, {406, 242}, {406, 305}, {406, 159}, {406, 77}, {9, 309}, {148, 401}, {148, 65}, {148, 218}, {148, 342}, {148, 331}, {148, 339}, {51, 290}, {51, 150}, {51, 60}, {51, 137}, {51, 160}, {51, 252}, {51, 364}, {51, 335}, {51, 343}, {51, 304}, {102, 180}, {102, 138}, {110, 74}, {110, 171}, {110, 390}, {110, 352}, {110, 37}, {370, 377}, {370, 358}, {370, 36}, {370, 272}, {125, 66}, {125, 301}, {125, 67}, {125, 239}, {125, 175}, {357, 12}, {357, 106}, {357, 282}, {357, 240}, {360, 144}, {360, 393}, {360, 317}, {360, 195}, {260, 264}, {260, 13}, {260, 281}, {260, 400}, {260, 212}, {260, 365}, {260, 402}, {260, 63}, {260, 255}, {196, 193}, {196, 338}, {228, 399}, {228, 202}, {228, 313}, {228, 392}, {228, 208}, {228, 38}, {228, 31}, {103, 203}, {103, 320}, {103, 254}, {103, 275}, {103, 34}, {347, 149}, {347, 222}, {347, 114}, {347, 157}, {347, 325}, {347, 6}, {347, 154}, {347, 250}, {347, 350}, {384, 93}, {384, 123}, {384, 374}, {384, 50}, {25, 285}, {25, 20}, {25, 288}, {25, 251}, {25, 185}, {25, 289}, {3, 241}, {3, 258}, {3, 43}, {140, 58}, {140, 329}, {140, 45}, {140, 287}, {140, 132}, {140, 170}, {140, 355}, {140, 311}, {140, 47}, {140, 168}, {56, 321}, {56, 388}, {56, 32}, {56, 302}, {56, 190}, {56, 48}, {56, 11}, {263, 96}, {263, 30}, {263, 24}, {263, 26}, {231, 229}, {231, 164}, {231, 128}, {231, 295}, {231, 230}, {231, 396}, {231, 81}, {231, 244}, {231, 276}, {231, 141}, {326, 134}, {326, 161}, {326, 97}, {326, 286}, {326, 88}, {326, 221}, {326, 405}, {326, 8}, {326, 156}, {121, 113}, {121, 15}, {121, 348}, {121, 104}, {121, 398}, {121, 91}, {121, 40}, {121, 64}, {121, 318}, {121, 111}, {116, 271}, {21, 83}, {21, 55}, {262, 368}, {262, 336}, {262, 249}, {262, 129}, {262, 145}, {262, 337}, {262, 234}, {262, 79}, {369, 90}, {369, 122}, {369, 395}, {369, 108}, {369, 341}, {369, 334}, {369, 316}, {369, 69}, {369, 278}, {183, 151}, {183, 315}, {183, 17}, {183, 178}, {183, 274}, {183, 269}, {75, 200}, {75, 131}, {75, 126}, {75, 19}, {75, 359}, {75, 70}, {75, 133}, {75, 117}, {75, 33}, {75, 206}, {303, 223}, {303, 324}, {303, 101}, {303, 314}, {303, 135}, {303, 146}, {330, 191}, {330, 194}, {330, 253}, {330, 307}, {330, 225}, {330, 299}, {330, 382}, {330, 82}, {397, 167}, {397, 2}, {397, 308}, {397, 246}, {397, 245}, {397, 265}, {35, 261}, {35, 328}, {35, 224}, {35, 296}, {35, 340}, {35, 186}, {35, 280}, {279, 210}, {279, 4}, {279, 268}, {279, 173}, {279, 284}, {279, 247}, {279, 119}, {279, 89}, {279, 205}, {345, 10}, {345, 124}, {345, 366}, {345, 7}, {345, 98}, {345, 209}, {345, 394}, {345, 385}, {345, 188}, {345, 166}, {139, 153}, {139, 327}, {139, 127}, {139, 155}, {139, 312}, {391, 235}, {391, 76}, {391, 381}, {266, 219}, {266, 5}, {266, 361}, {266, 120}, {266, 344}, {266, 105}, {266, 371}, {266, 165}, {266, 323}, {16, 59}, {16, 237}, {16, 291}, {16, 109}, {214, 383}, {214, 142}, {214, 220}, {214, 215}, {184, 78}, {184, 238}, {184, 57}, {68, 204}, {27, 356}, {27, 322}, {27, 62}, {27, 162}, {27, 407}, {27, 14}, {27, 152}, {27, 86}, {27, 84}, {27, 95}, {192, 42}, {87, 115}, {87, 403}, {87, 118}, {87, 189}, {87, 28}, {87, 277}, {87, 147}, {87, 49}, {39, 73}, {386, 213}, {386, 387}, {386, 306}, {386, 346}, {386, 143}, {386, 363}, {386, 41}, {386, 373}, {259, 216}, {259, 372}, {259, 169}, {259, 248}, {259, 354}, {259, 53}, {259, 44}, {259, 380}, {259, 256}, {94, 333}, {94, 172}, {94, 298}, {94, 18}, {94, 232}, {94, 158}, {94, 207}, {94, 236}, {112, 310}, {112, 130}, {112, 319}, {112, 174}, {99, 177}, {99, 233}, {99, 187}, {99, 198}, {99, 375}, {99, 201}, {99, 176}, {99, 294}, {99, 379}};
int[][] o = new int[][]{
{1, 201, 26}, {1, 114, 22}, {2, 366, 42}, {2, 116, 22}, {1, 239, 5}, {1, 11, 38}, {1, 50, 19}, {2, 159, 45}, {1, 242, 12}, {1, 338, 44}, {1, 221, 33}, {2, 268, 21}, {3, 186}, {1, 171, 46}, {2, 41, 15}, {2, 84, 1}, {1, 210, 30}, {2, 109, 28}, {2, 164, 16}, {2, 40, 8}, {1, 129, 30}, {3, 268}, {2, 163, 16}, {2, 345, 44}, {1, 91, 13}, {2, 16, 46}, {2, 304, 15}, {2, 387, 8}, {2, 296, 13}, {1, 293, 1}, {2, 362, 15}, {2, 177, 37}, {1, 11, 50}, {1, 372, 34}, {3, 1}, {3, 268}, {1, 339, 43}, {2, 353, 45}, {2, 121, 19}, {3, 1}, {1, 125, 8}, {1, 160, 44}, {1, 66, 43}, {1, 98, 2}, {3, 52}, {2, 108, 41}, {3, 245}, {1, 66, 45}, {3, 52}, {1, 132, 49}, {2, 135, 32}, {3, 402}, {3, 1}, {2, 234, 23}, {2, 80, 50}, {3, 52}, {3, 283}, {2, 233, 26}, {2, 269, 27}, {1, 388, 45}, {2, 139, 40}, {2, 118, 17}, {2, 329, 37}, {2, 200, 27}, {3, 1}, {1, 9, 23}, {2, 367, 32}, {3, 52}, {2, 314, 23}, {1, 50, 2}, {3, 283}, {1, 320, 25}, {3, 154}, {1, 270, 48}, {1, 213, 30}, {2, 297, 12}, {2, 404, 20}, {3, 283}, {2, 291, 31}, {3, 52}, {1, 278, 43}, {1, 244, 45}, {1, 96, 3}, {3, 1}, {1, 339, 49}, {1, 131, 26}, {2, 75, 9}, {1, 80, 39}, {3, 264}, {1, 69, 7}, {1, 394, 37}, {2, 17, 16}, {1, 290, 44}, {1, 95, 35}, {3, 52}, {2, 361, 8}, {1, 195, 18}, {1, 63, 15}, {3, 52}, {1, 309, 8}, {2, 368, 28}, {3, 1}, {3, 1}, {1, 311, 48}, {3, 125}, {1, 382, 23}, {2, 225, 23}, {2, 309, 24}, {3, 253}, {1, 66, 18}, {2, 137, 26}, {3, 269}, {3, 283}, {3, 283}, {1, 346, 10}, {1, 340, 19}, {1, 105, 13}, {1, 303, 25}, {1, 376, 30}, {3, 52}, {1, 275, 36}, {1, 9, 3}, {1, 190, 36}, {1, 312, 10}, {3, 366}, {1, 248, 24}, {1, 360, 41}, {3, 1}, {3, 1}, {2, 367, 27}, {1, 209, 19}, {2, 255, 3}, {2, 135, 42}, {1, 57, 16}, {2, 121, 8}, {3, 221}, {1, 112, 47}, {2, 42, 23}, {2, 87, 12}, {1, 293, 27}, {1, 309, 28}, {1, 33, 7}, {1, 196, 39}, {3, 314}, {1, 164, 12}, {2, 2, 31}, {3, 52}, {1, 80, 40}, {3, 52}, {3, 283}, {3, 1}, {2, 212, 16}, {3, 1}, {3, 52}, {2, 50, 43}, {3, 1}, {1, 14, 42}, {3, 283}, {2, 404, 32}, {3, 283}, {2, 44, 11}, {2, 70, 18}, {2, 147, 32}, {2, 260, 28}, {1, 144, 9}, {3, 52}, {3, 1}, {3, 283}, {3, 283}, {1, 329, 20}, {1, 45, 13}, {3, 52}, {1, 340, 33}, {2, 14, 11}, {1, 288, 31}, {1, 262, 46}, {1, 145, 42}, {2, 303, 24}, {1, 392, 3}, {1, 295, 24}, {2, 213, 5}, {1, 368, 13}, {1, 228, 14}, {1, 375, 47}, {3, 283}, {3, 161}, {3, 1}, {1, 64, 46}, {2, 102, 5}, {1, 251, 21}, {3, 298}, {1, 223, 24}, {2, 297, 13}, {1, 293, 19}, {2, 99, 26}, {2, 395, 21}, {3, 52}, {3, 52}, {3, 52}, {2, 221, 50}, {3, 1}, {2, 116, 41}, {2, 246, 24}, {1, 233, 39}, {3, 1}, {2, 318, 5}, {2, 63, 43}, {1, 142, 46}, {2, 367, 38}, {2, 193, 47}, {1, 34, 27}, {1, 302, 25}, {3, 1}, {1, 238, 13}, {2, 372, 19}, {3, 311}, {1, 3, 14}, {2, 200, 34}, {3, 52}, {2, 160, 40}, {2, 242, 30}, {1, 273, 27}, {1, 375, 9}, {3, 52}, {1, 66, 15}, {1, 103, 8}, {3, 52}, {1, 400, 48}, {2, 327, 46}, {1, 379, 25}, {2, 164, 4}, {2, 358, 4}, {2, 356, 1}, {2, 175, 7}, {2, 261, 37}, {3, 283}, {1, 155, 7}, {2, 214, 9}, {1, 154, 42}, {1, 12, 22}, {3, 52}, {1, 273, 8}, {3, 52}, {3, 52}, {3, 52}, {1, 364, 38}, {2, 199, 30}, {3, 283}, {1, 70, 18}, {2, 275, 41}, {2, 373, 3}, {2, 260, 2}, {2, 31, 11}, {2, 326, 1}, {2, 244, 34}, {3, 323}, {2, 209, 27}, {1, 163, 5}, {1, 131, 45}, {1, 3, 44}, {2, 311, 34}, {1, 8, 35}, {1, 78, 49}, {2, 342, 32}, {2, 231, 46}, {2, 124, 23}, {1, 85, 30}, {2, 274, 16}, {1, 28, 39}, {3, 283}, {1, 156, 28}, {3, 54}, {1, 100, 1}, {1, 43, 9}, {3, 1}, {2, 85, 3}, {3, 149}, {3, 1}, {3, 187}, {2, 107, 12}, {1, 374, 9}, {3, 52}, {3, 52}, {3, 283}, {3, 1}, {3, 283}, {2, 365, 10}, {1, 89, 27}, {3, 52}, {2, 145, 44}, {1, 220, 33}, {2, 116, 8}, {1, 94, 26}, {3, 283}, {3, 52}, {3, 371}, {2, 185, 29}, {1, 93, 37}, {2, 203, 36}, {2, 181, 46}, {1, 313, 14}, {3, 283}, {2, 191, 34}, {3, 283}, {1, 206, 6}, {3, 235}, {1, 56, 31}, {2, 361, 11}, {1, 244, 27}, {2, 241, 12}, {1, 214, 41}, {2, 358, 20}, {1, 340, 37}, {2, 126, 18}, {2, 101, 44}, {1, 23, 46}, {2, 323, 24}, {3, 52}, {1, 301, 12}, {2, 224, 43}, {1, 24, 26}, {2, 326, 50}, {3, 52}, {3, 52}, {3, 52}, {2, 177, 37}, {1, 240, 41}, {1, 320, 12}, {3, 239}, {2, 369, 31}, {1, 372, 19}, {2, 179, 23}, {2, 180, 23}, {1, 170, 10}, {1, 252, 1}, {2, 42, 39}, {2, 124, 13}, {1, 263, 19}, {1, 244, 1}, {1, 84, 37}, {1, 187, 8}, {3, 283}, {2, 175, 43}, {1, 203, 38}, {3, 1}, {2, 19, 29}, {1, 301, 19}, {3, 41}, {3, 46}, {2, 26, 21}, {1, 325, 7}, {1, 343, 47}, {2, 81, 49}, {2, 395, 29}, {3, 52}, {3, 283}, {2, 114, 47}, {2, 6, 38}, {1, 219, 37}, {2, 154, 23}, {1, 188, 6}, {1, 116, 25}, {2, 385, 7}, {1, 289, 3}, {2, 295, 2}, {3, 1}, {3, 1}, {3, 52}, {3, 283}, {3, 52}, {2, 140, 2}, {3, 1}, {1, 248, 40}, {1, 379, 18}, {1, 224, 7}, {2, 63, 24}, {3, 283}, {2, 207, 13}, {1, 333, 6}, {2, 332, 20}, {3, 222}, {2, 52, 14}, {1, 158, 4}, {3, 52}, {1, 271, 35}, {1, 75, 10}, {2, 322, 11}, {2, 315, 3}, {2, 26, 7}, {1, 10, 11}, {2, 401, 50}, {1, 9, 18}, {3, 1}, {1, 28, 39}, {1, 185, 3}, {3, 52}, {1, 162, 20}, {1, 247, 5}, {3, 52}, {1, 308, 9}, {2, 103, 33}, {3, 1}, {3, 344}, {3, 283}, {2, 124, 29}, {3, 1}, {2, 121, 23}, {1, 122, 23}, {1, 381, 37}, {2, 185, 35}, {2, 285, 5}, {2, 190, 25}, {2, 122, 25}, {1, 293, 38}, {1, 75, 41}, {2, 138, 15}, {1, 202, 9}, {1, 121, 42}, {3, 52}, {2, 83, 23}, {3, 325}, {3, 1}, {2, 350, 41}, {2, 337, 50}, {2, 198, 19}, {1, 221, 32}, {1, 309, 4}, {3, 1}, {1, 310, 44}, {2, 22, 34}, {1, 247, 29}, {2, 187, 22}, {3, 283}, {1, 366, 16}, {3, 52}, {3, 52}, {1, 8, 36}, {2, 83, 18}, {1, 134, 36}, {2, 291, 27}, {2, 352, 16}, {2, 281, 27}, {1, 397, 15}, {2, 215, 40}, {2, 190, 4}, {2, 98, 17}, {3, 331}, {2, 21, 32}, {1, 56, 10}, {1, 388, 42}, {1, 225, 3}, {1, 225, 42}, {1, 185, 18}, {3, 347}, {1, 184, 23}, {3, 52}, {1, 137, 30}, {1, 187, 39}, {1, 249, 46}, {1, 137, 16}, {1, 160, 7}, {2, 148, 11}, {1, 384, 13}, {2, 389, 27}, {2, 308, 16}, {2, 384, 39}, {2, 235, 1}, {2, 117, 6}, {2, 222, 11}, {3, 1}, {3, 52}, {1, 249, 5}, {2, 321, 28}, {2, 365, 14}, {2, 2, 34}, {3, 362}, {3, 52}, {2, 93, 25}, {3, 1}, {2, 359, 10}, {3, 52}, {3, 1}, {2, 408, 4}, {1, 193, 45}, {3, 52}, {1, 97, 11}, {1, 75, 2}, {3, 1}, {3, 52}, {3, 283}, {3, 273}, {3, 105}, {1, 95, 14}, {3, 1}, {3, 100}, {2, 176, 33}, {2, 121, 26}, {3, 52}, {1, 331, 21}, {2, 83, 14}};
Util.printArray(bonus.bonus(408 ,l,o));
}
private int mod = 1000000007;
/**
* 解题思路：
* 1、构建树及依赖关系
* 2、按操作赋值
* 3、保存取值结果
* <p>
* 比较{@link _5_bonus}优化：、
* 发团队币，全部发给团队负责人，负责人统一保存
* 1、为了让取币总和更快，在发币的时候就保存了团队币总和
* 2、由于发币团队成员都是一致的，所以负责人中可以保存下属的同样的币（每个人还可以有自己特有的币）
*
* 执行用时 :47 ms , 在所有 Java 提交中击败了93.62% 的用户
* 内存消耗 :89.6 MB, 在所有 Java 提交中击败了100.00%的用户
*
* @param n
* @param leadership
* @param operations
* @return
*/
public int[] bonus(int n, int[][] leadership, int[][] operations) {
List<Integer> retList = new ArrayList<>();
//创建树
CoinTree[] trees = new CoinTree[n + 1];
for (int i = 1; i <= n; i++) {
trees[i] = new CoinTree(i);
}
//构造依赖关系
for (int i = 0; i < leadership.length; i++) {
int[] item = leadership[i];
//计算团队成员
CoinTree parent = trees[item[0]];
trees[item[1]].parent = parent;
while (parent != null) {
parent.teamSize++;
parent = parent.parent;
}
}
//操作
for (int i = 0; i < operations.length; i++) {
int[] item = operations[i];
//操作类型
int operation = item[0];
switch (operation) {
case 1://给某个人发币
addPersonCoin(trees[item[1]], item[2]);
break;
case 2://给某个人和他的团队发币
addTeamCoin(trees[item[1]], item[2]);
break;
case 3://计算某个人和他的团队币总和，并记录返回
retList.add(getTeamCoin(trees[item[1]]));
break;
}
}
//list to array
int[] retArr = new int[retList.size()];
for (int i = 0; i < retList.size(); i++) {
retArr[i] = retList.get(i);
}
return retArr;
}
private int getTeamCoin(CoinTree tree) {
long result = tree.teamCoinAll;
int size = tree.teamSize;
CoinTree parent = tree.parent;
while (parent != null) {
result += parent.teamCoin * size;
parent = parent.parent;
}
return (int) (result % mod);
}
private void addPersonCoin(CoinTree tree, int coin) {
tree.teamCoinAll += coin;
CoinTree parent = tree.parent;
while (parent != null) {
parent.teamCoinAll += coin;
parent = parent.parent;
}
}
private void addTeamCoin(CoinTree tree, int coin) {
tree.teamCoin += coin;
int teamAddCoin = coin * tree.teamSize;
tree.teamCoinAll += teamAddCoin;
CoinTree parent = tree.parent;
while (parent != null) {
parent.teamCoinAll += teamAddCoin;
parent = parent.parent;
}
}
class CoinTree {
int value;
int teamSize; //团队成员（包括自己）
long teamCoin; //团队每个人共有
long teamCoinAll;//团队总共有的
CoinTree parent;
public CoinTree(int value) {
this.value = value;
teamSize = 1;//自己
}
}
}