結果
問題 | No.1038 TreeAddQuery |
ユーザー |
![]() |
提出日時 | 2020-03-18 02:34:51 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 2,301 ms / 4,000 ms |
コード長 | 5,195 bytes |
コンパイル時間 | 1,092 ms |
コンパイル使用メモリ | 116,608 KB |
実行使用メモリ | 71,808 KB |
最終ジャッジ日時 | 2024-11-25 04:41:56 |
合計ジャッジ時間 | 31,757 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
コンパイルメッセージ
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;using System.IO;class Program{Scanner cin;Printer cout;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();cout = new Printer();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);cout.printArray(ans);}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]);bit.add(rest + 1, -C[q]);}}prop.Clear();foreach (var to in g[centroid]){if (used[to]) continue;d = add_dfs(to, centroid, 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]);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 int[] nextArrayInt(int N, int add = 0){int[] ret = new int[N];for (int i = 0; i < N; i++){ret[i] = nextInt() + add;}return ret;}public long nextLong(){return long.Parse(next());}public long[] nextArrayLong(int N, long add = 0){long[] ret = new long[N];for (int i = 0; i < N; i++){ret[i] = nextLong() + add;}return ret;}public double nextDouble(){return double.Parse(next());}public double[] nextArrayDouble(int N, double add = 0){double[] ret = new double[N];for (int i = 0; i < N; i++){ret[i] = nextDouble() + add;}return ret;}}class Printer{public Printer(){var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(sw);}~Printer() => flush();public void println(string a) => Console.WriteLine(a);public void println<T>(IEnumerable<T> a) => println(string.Join(" ", a));public void println(params object[] a) => println(string.Join(" ", a));public void print<T>(string a) => Console.Write(a);public void print<T>(IEnumerable<T> a) => print(string.Join(" ", a));public void print(params object[] a) => print(string.Join(" ", a));public void printArray<T>(params T[] a){foreach (var x in a) Console.WriteLine(x);}public void flush() => Console.Out.Flush();}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;}}