結果
問題 | No.1038 TreeAddQuery |
ユーザー |
![]() |
提出日時 | 2020-03-15 23:16:08 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,928 bytes |
コンパイル時間 | 1,629 ms |
コンパイル使用メモリ | 110,616 KB |
実行使用メモリ | 69,748 KB |
最終ジャッジ日時 | 2024-10-15 01:59:50 |
合計ジャッジ時間 | 35,277 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 WA * 18 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;class Program{Scanner cin;int N, Q;int[] A, B, C;List<int>[] g, qs;int[] sub, dep;long[] ans;bool[] used;BinaryIndexedTree bit;List<int> prop;void myon(){cin = new Scanner();N = cin.nextInt();Q = cin.nextInt();g = new List<int>[N];qs = new List<int>[N];sub = new int[N];dep = new int[N];used = new bool[N];A = new int[Q];B = new int[Q];C = new int[Q];ans = new long[Q];prop = new List<int>();for (int i = 0; i < N; i++){g[i] = new List<int>();qs[i] = new List<int>();}for (int i = 1; i < N; i++){int a = cin.nextInt() - 1;int b = cin.nextInt() - 1;g[a].Add(b);g[b].Add(a);}for (int i = 0; i < Q; i++){A[i] = cin.nextInt() - 1;B[i] = cin.nextInt();C[i] = cin.nextInt();qs[A[i]].Add(i);}build(0);foreach (var i in ans){Console.WriteLine(i);}}int build_dfs(int idx, int par){sub[idx] = 1;foreach (var to in g[idx]){if (to == par || used[to]) continue;sub[idx] += build_dfs(to, idx);}return sub[idx];}int search_centroid(int idx, int par, int mid){foreach (var to in g[idx]){if (to == par || used[to]) continue;if (sub[to] > mid) return search_centroid(to, idx, mid);}return idx;}int add_dfs(int idx, int par, int d){dep[idx] = d;int max_d = d;foreach (var q in qs[idx]){prop.Add(q);}foreach (var to in g[idx]){if (to == par || used[to]) continue;max_d = Math.Max(max_d, add_dfs(to, idx, d + 1));}return max_d;}void build(int idx){int centroid = search_centroid(idx, -1, build_dfs(idx, -1) / 2);used[centroid] = true;int d = add_dfs(centroid, -1, 0);bit = new BinaryIndexedTree(d + 1);prop.Sort();foreach (var q in prop){ans[q] += bit.query(dep[A[q]]);int rest = B[q] - dep[A[q]];if (rest >= 0){bit.add(0, C[q]);if(rest + 1 <= d) bit.add(rest + 1, -C[q]);}}prop.Clear();foreach(var to in g[centroid]){if (used[to]) continue;d = add_dfs(to, idx, 1);bit = new BinaryIndexedTree(d + 1);prop.Sort();foreach (var q in prop){ans[q] -= bit.query(dep[A[q]]);int rest = B[q] - dep[A[q]];if (rest >= 0){bit.add(0, C[q]);if (rest + 1 <= d) bit.add(rest + 1, -C[q]);}}prop.Clear();}foreach (var to in g[centroid]){if (used[to]) continue;build(to);}}static void Main(string[] args){new Program().myon();}}class Scanner{string[] s;int i;readonly char[] cs = new char[] { ' ' };public Scanner(){s = new string[0];i = 0;}public string next(){if (i < s.Length) return s[i++];string st = Console.ReadLine();while (st == "") st = Console.ReadLine();s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);if (s.Length == 0) return next();i = 0;return s[i++];}public string nextLine(){return Console.ReadLine();}public int nextInt(){return int.Parse(next());}public long nextLong(){return long.Parse(next());}public double nextDouble(){return double.Parse(next());}}class BinaryIndexedTree{long[] data;public BinaryIndexedTree(int sz){data = new long[sz + 1];}public void add(int k, long x){for (++k; k < data.Length; k += k & -k){data[k] += x;}}public long query(int k){long ret = 0;for (++k; k > 0; k -= k & -k){ret += data[k];}return ret;}}