結果

問題 No.1038 TreeAddQuery
ユーザー ei1333333ei1333333
提出日時 2020-03-15 23:22:25
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 3,894 bytes
コンパイル時間 876 ms
コンパイル使用メモリ 111,328 KB
実行使用メモリ 71,804 KB
最終ジャッジ日時 2024-10-15 02:01:10
合計ジャッジ時間 34,874 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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.

ソースコード

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

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