結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 eitaho
|
| 提出日時 | 2016-07-18 18:26:37 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 2,096 ms / 10,000 ms |
| コード長 | 10,117 bytes |
| コンパイル時間 | 3,853 ms |
| コンパイル使用メモリ | 115,972 KB |
| 実行使用メモリ | 140,176 KB |
| 最終ジャッジ日時 | 2024-10-15 17:00:03 |
| 合計ジャッジ時間 | 11,590 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using Enu = System.Linq.Enumerable;
public class Program
{
static readonly int Mod = (int)1e9 + 7;
static void Add(ref int a, int b) { if ((a += b) >= Mod) a -= Mod; }
public void Solve()
{
int N = Reader.Int();
var HL = new HeavyLightDecomposition(N);
var Cost = Reader.IntArray(N);
var Mult = Reader.IntArray(N);
var E = Reader.IntTable(N - 1);
int Q = Reader.Int();
var table = Reader.IntTable(Q);
foreach (var e in E) HL.AddEdge(--e[0], --e[1]);
HL.Build(Cost, Mult);
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
foreach (var q in table)
if (q[0] == 0)
HL.Add(--q[1], --q[2], q[3]);
else
Console.WriteLine(HL.Sum(--q[1], --q[2]));
Console.Out.Flush();
}
class HeavyLightDecomposition
{
public readonly int N;
List<int>[] E;
int[] Y, X, Size, Parent;
List<List<int>> Path = new List<List<int>>();
List<int> PathDepth = new List<int>();
RangeAddSumSegTree[] seg;
BinaryIndexedTree[] BIT;
void Init(int[] initialCost, int[] mult)
{
seg = new RangeAddSumSegTree[Path.Count];
BIT = new BinaryIndexedTree[Path.Count];
for (int i = 0; i < seg.Length; i++)
{
var C = new int[Path[i].Count];
for (int x = 0; x < Path[i].Count; x++)
C[x] = mult[Path[i][x]];
seg[i] = new RangeAddSumSegTree(Path[i].Count, C);
BIT[i] = new BinaryIndexedTree(Path[i].Count, Mod);
for (int x = 0; x < Path[i].Count; x++)
BIT[i].Add(x, initialCost[Path[i][x]]);
}
}
public void Add(int a, int b, long val)
{
int pa = Y[a], pb = Y[b];
if (pa == pb)
seg[pa].Add(Math.Min(X[a], X[b]), Math.Max(X[a], X[b]) + 1, val);
else if (PathDepth[pa] >= PathDepth[pb])
{
seg[pa].Add(0, X[a] + 1, val);
Add(Parent[Path[pa][0]], b, val);
}
else
{
seg[pb].Add(0, X[b] + 1, val);
Add(Parent[Path[pb][0]], a, val);
}
}
public long Sum(int a, int b)
{
int pa = Y[a], pb = Y[b];
if (pa == pb)
{
int L = Math.Min(X[a], X[b]);
int R = Math.Max(X[a], X[b]) + 1;
return (BIT[pa].Sum(L, R) + seg[pa].Sum(L, R)) % Mod;
}
if (PathDepth[pa] >= PathDepth[pb])
{
return (BIT[pa].Sum(0, X[a] + 1) + seg[pa].Sum(0, X[a] + 1) + Sum(Parent[Path[pa][0]], b)) % Mod;
}
return (BIT[pb].Sum(0, X[b] + 1) + seg[pb].Sum(0, X[b] + 1) + Sum(Parent[Path[pb][0]], a)) % Mod;
}
public HeavyLightDecomposition(int n)
{
N = n;
Y = new int[N]; X = new int[N];
Size = new int[N]; Parent = new int[N];
E = new List<int>[N];
for (int i = 0; i < N; i++) E[i] = new List<int>();
}
public void AddEdge(int a, int b)
{
E[a].Add(b);
E[b].Add(a);
}
public void Build(int[] initialCost, int[] mult, int root = 0)
{
CountNodes();
CompressPath();
Init(initialCost, mult);
}
void CountNodes()
{
var stack = new Stack<int>();
var nodes = new int[N];
int ni = N - 1;
stack.Push(0);
while (stack.Count > 0)
{
int a = stack.Pop();
for (int ei = 0; ei < E[a].Count; ei++)
{
int b = E[a][ei];
if (b == Parent[a]) { E[a].RemoveAt(ei); ei--; }
else { Parent[b] = a; stack.Push(b); }
}
nodes[ni--] = a;
}
foreach (int a in nodes)
{
Size[a] = 1;
var e = E[a];
for (int i = 0; i < e.Count; i++)
{
int b = E[a][i];
Size[a] += Size[b];
if (Size[b] > Size[e[0]]) { int t = e[0]; e[0] = b; e[i] = t; }
}
}
}
void CompressPath()
{
var stack = new Stack<long>();
stack.Push(0);
Path.Add(new List<int>());
PathDepth.Add(0);
while (stack.Count > 0)
{
long mask = stack.Pop();
int a = (int)(mask >> 32);
int pathId = (int)mask;
Y[a] = pathId;
X[a] = Path[pathId].Count;
Path[pathId].Add(a);
if (E[a].Count == 0) continue;
for (int i = E[a].Count - 1; i > 0; i--)
{
Path.Add(new List<int>());
PathDepth.Add(PathDepth[pathId] + 1);
stack.Push(((long)E[a][i] << 32) + Path.Count - 1);
}
stack.Push(((long)E[a][0] << 32) + pathId);
}
}
public int LCA(int a, int b)
{
int pa = Y[a], pb = Y[b];
if (pa == pb) return (X[a] < X[b]) ? a : b;
if (PathDepth[pa] >= PathDepth[pb]) return LCA(Parent[Path[pa][0]], b);
return LCA(a, Parent[Path[pb][0]]);
}
}
class RangeAddSumSegTree
{
public readonly int N;
private readonly long[] V, S, M;
public RangeAddSumSegTree(int n, int[] mult)
{
for (N = 2; N < n; ) N *= 2;
V = new long[N * 2];
S = new long[N * 2];
M = new long[N + 1];
for (int i = 0; i < mult.Length; i++)
M[i + 1] = (M[i] + mult[i]) % Mod;
}
public long Sum(int L, int R) { return Sum(0, 0, N, L, R); }
private long Sum(int i, int currL, int currR, int L, int R)
{
if (currL >= R || currR <= L) return 0;
if (currL >= L && currR <= R)
return (S[i] + V[i] * ((M[currR] - M[currL]) % Mod + Mod)) % Mod;
int a = Math.Max(currL, L);
int b = Math.Min(currR, R);
long res = V[i] * ((M[b] - M[a]) % Mod + Mod) % Mod;
int mid = (currL + currR) / 2;
res = (res + Sum(i * 2 + 1, currL, mid, L, R)) % Mod;
res = (res + Sum(i * 2 + 2, mid, currR, L, R)) % Mod;
return res;
}
public void Add(int L, int R, long val) { Add(0, val, 0, N, L, R); }
private void Add(int i, long val, int currL, int currR, int L, int R)
{
if (currL >= R || currR <= L) return;
if (currL >= L && currR <= R) { V[i] = (V[i] + val) % Mod; return; }
int a = Math.Max(currL, L);
int b = Math.Min(currR, R);
S[i] = (S[i] + val * ((M[b] - M[a]) % Mod + Mod) % Mod) % Mod;
int mid = (currL + currR) / 2;
Add(i * 2 + 1, val, currL, mid, L, R);
Add(i * 2 + 2, val, mid, currR, L, R);
}
}
class BinaryIndexedTree
{
private readonly int N;
private readonly int Mod;
private readonly int[] A;
public BinaryIndexedTree(int N, int mod)
{
this.N = N + 1;
Mod = mod;
A = new int[N + 2];
}
public void Add(int i, int val)
{
for (++i; i <= N; i += i & -i) ModAdd(ref A[i], val);
}
public int Sum(int i)
{
int sum = 0;
for (++i; i > 0; i &= i - 1) ModAdd(ref sum, A[i]);
return sum;
}
public long Sum(int L, int R) // [L, R)
{
return (Sum(R - 1) - Sum(L - 1) + Mod) % Mod;
}
private void ModAdd(ref int a, int b) { a += b; if (a >= Mod) a -= Mod; }
}
}
class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
static TextReader reader = Console.In;
static readonly char[] separator = { ' ' };
static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
static string[] A = new string[0];
static int i;
static void Init() { A = new string[0]; }
public static void Set(TextReader r) { reader = r; Init(); }
public static void Set(string file) { reader = new StreamReader(file); Init(); }
public static bool HasNext() { return CheckNext(); }
public static string String() { return Next(); }
public static int Int() { return int.Parse(Next()); }
public static long Long() { return long.Parse(Next()); }
public static double Double() { return double.Parse(Next()); }
public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
public static int[] IntArray(int N) { return Range(N, Int); }
public static int[][] IntTable(int H) { return Range(H, IntLine); }
public static string[] StringArray(int N) { return Range(N, Next); }
public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
public static string Line() { return reader.ReadLine().Trim(); }
static string[] Split(string s) { return s.Split(separator, op); }
static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()); return r; }
static string Next() { CheckNext(); return A[i++]; }
static bool CheckNext()
{
if (i < A.Length) return true;
string line = reader.ReadLine();
if (line == null) return false;
if (line == "") return CheckNext();
A = Split(line);
i = 0;
return true;
}
}