結果

問題 No.1038 TreeAddQuery
ユーザー ei1333333ei1333333
提出日時 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.

ソースコード

diff #
プレゼンテーションモードにする

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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0