結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
👑  hos.lyric
|
| 提出日時 | 2020-04-25 15:54:58 |
| 言語 | D (dmd 2.109.1) |
| 結果 |
AC
|
| 実行時間 | 3,552 ms / 4,000 ms |
| コード長 | 6,502 bytes |
| コンパイル時間 | 1,101 ms |
| コンパイル使用メモリ | 129,152 KB |
| 実行使用メモリ | 195,184 KB |
| 最終ジャッジ日時 | 2024-06-22 06:48:09 |
| 合計ジャッジ時間 | 47,791 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
import std.conv, std.functional, std.range, std.stdio, std.string;import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;import core.bitop;class EOFException : Throwable { this() { super("EOF"); } }string[] tokens;string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }int readInt() { return readToken.to!int; }long readLong() { return readToken.to!long; }real readReal() { return readToken.to!real; }bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1;(unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }void bAdd(T)(T[] bit, int pos, T val)in {assert(0 <= pos && pos < bit.length, "bAdd: 0 <= pos < |bit| must hold");}do {for (int x = pos; x < bit.length; x |= x + 1) {bit[x] += val;}}// sum of [0, pos)T bSum(T)(T[] bit, int pos)in {assert(0 <= pos && pos <= bit.length, "bSum: 0 <= pos <= |bit| must hold");}do {T ret = 0;for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) {ret += bit[x];}return ret;}int N;int[] A, B;int[][] G;int bitLen;int[][] rss, jss, dss, poss;int[][] ptrR;int[][][] ptrs;void solveCentroidDecomp() {auto sz = new int[N];auto del = new bool[N];void dfsSz(int u, int p) {sz[u] = 1;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (v != p) {dfsSz(v, u);sz[u] += sz[v];}}}dfsSz(0, -1);// r: centroidvoid solveSubtree(int r) {debug {string dfsDebug(int u, int p) {string ret = u.to!string;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (!del[v] && v != p) {ret ~= "(" ~ dfsDebug(v, u) ~ ")";}}return ret;}writeln("solveSubtree ", dfsDebug(r, -1));}//int[] vs;foreach (i; G[r]) {const v = A[i] ^ B[i] ^ r;if (!del[v]) {vs ~= v;}}const vsLen = cast(int)(vs.length);// BFSalias Entry = Tuple!(int, "d", int, "u", int, "p", int, "j");Entry[] que;auto ess = new Entry[][vsLen];que ~= Entry(0, r, -1, -1);foreach (j; 0 .. vsLen) {que ~= Entry(1, vs[j], r, j);ess[j] ~= Entry(1, vs[j], r, j);}for (int qb = 1; qb < que.length; ) {const d = que[qb].d;const u = que[qb].u;const p = que[qb].p;const j = que[qb].j;++qb;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (!del[v] && v != p) {que ~= Entry(d + 1, v, u, j);ess[j] ~= Entry(d + 1, v, u, j);}}}foreach (ref e; que) {rss[e.u] ~= r;jss[e.u] ~= e.j;dss[e.u] ~= e.d;}{const dLim = que[$ - 1].d + 1;ptrR[r] = new int[dLim + 1];int x;foreach (d; 0 .. dLim) {ptrR[r][d] = bitLen;for (; x < que.length && que[x].d == d; ++x) {poss[que[x].u] ~= bitLen++;}}ptrR[r][dLim] = bitLen;}ptrs[r] = new int[][vsLen];foreach (j; 0 .. vsLen) {const dLim = ess[j][$ - 1].d + 1;ptrs[r][j] = new int[dLim + 1];int x;foreach (d; 0 .. dLim) {ptrs[r][j][d] = bitLen;for (; x < ess[j].length && ess[j][x].d == d; ++x) {poss[ess[j][x].u] ~= bitLen++;}}ptrs[r][j][dLim] = bitLen;}//}void solveRec(int u) {for (; ; ) {int vm = -1;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (!del[v]) {if (vm == -1 || sz[vm] < sz[v]) {vm = v;}}}if (vm == -1 || sz[u] >= 2 * sz[vm]) {solveSubtree(u);del[u] = true;foreach (i; G[u]) {const v = A[i] ^ B[i] ^ u;if (!del[v]) {solveRec(v);}}break;} else {sz[u] -= sz[vm];sz[vm] += sz[u];u = vm;}}}solveRec(0);}void main() {try {for (; ; ) {N = readInt();const Q = readInt();A = new int[N - 1];B = new int[N - 1];foreach (i; 0 .. N - 1) {A[i] = readInt() - 1;B[i] = readInt() - 1;}auto X = new int[Q];auto Y = new int[Q];auto Z = new long[Q];foreach (q; 0 .. Q) {X[q] = readInt() - 1;Y[q] = readInt();Z[q] = readLong();}G = new int[][N];foreach (i; 0 .. N - 1) {G[A[i]] ~= i;G[B[i]] ~= i;}bitLen = 0;rss = new int[][N];jss = new int[][N];dss = new int[][N];poss = new int[][N];ptrR = new int[][N];ptrs = new int[][][N];solveCentroidDecomp;debug {writeln("bitLen = ", bitLen);writeln("rss = ", rss);writeln("jss = ", jss);writeln("dss = ", dss);writeln("poss = ", poss);writeln("ptrR = ", ptrR);writeln("ptrs = ", ptrs);}auto bit = new long[bitLen + 1];void rangeAdd(int a, int b, long val) {debug {// writeln("rangeAdd ", a, " ", b, " ", val);}bit.bAdd(a, +val);bit.bAdd(b, -val);}foreach (q; 0 .. Q) {long ans;foreach (pos; poss[X[q]]) {ans += bit.bSum(pos + 1);}writeln(ans);const rsLen = cast(int)(rss[X[q]].length);foreach (k; 0 .. rsLen) {const r = rss[X[q]][k];const j = jss[X[q]][k];const d = dss[X[q]][k];if (Y[q] >= d) {const dd = Y[q] - d + 1;rangeAdd(ptrR[r][0], ptrR[r][min(dd, $ - 1)], Z[q]);if (j != -1) {rangeAdd(ptrs[r][j][0], ptrs[r][j][min(dd, $ - 1)], -Z[q]);}}}}}} catch (EOFException e) {}}