結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 kuuso1
|
| 提出日時 | 2023-05-07 17:21:03 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 4,265 ms / 10,000 ms |
| コード長 | 15,473 bytes |
| コンパイル時間 | 14,030 ms |
| コンパイル使用メモリ | 170,856 KB |
| 実行使用メモリ | 303,836 KB |
| 最終ジャッジ日時 | 2024-11-24 16:34:51 |
| 合計ジャッジ時間 | 31,727 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (82 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(11,8): warning CS8981: 型名 'monoid' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(265,9): warning CS8981: 型名 'mlong' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Text;
namespace yukicoder_235 {
using monoid = ValueTuple<mlong, mlong>;
class TEST {
public static void Main() {
Sol mySol = new Sol();
mySol.Solve();
}
}
class Sol {
public void Solve() {
var E = new List<int>[N];
for (int i = 0; i < N; i++) E[i] = new List<int>();
for(int i = 0; i < N - 1; i++) {
E[A[i]].Add(B[i]);
E[B[i]].Add(A[i]);
}
int root = 0;
var hld = new TreeDecompostion.HeavyLightDecompotion(N, E, root);
hld.Build();
// (s1,c1) ^z = (s1+c1*z, c1)
// {(s1, c1) + (s2, c2)} ^ z = {(s1+s2),(c1+c2)} ^ z
// = (s1+s2 + (c1+c2) * z, c1+c2) = (s1+c1*z,c1) + (s2+c2*z,c2) = (s1,c1)^z + (s2,c2)^z
Func<monoid, monoid, monoid> dot = (p, q) => ((p.Item1 + q.Item1), (p.Item2 + q.Item2));
monoid dotidentity = (0, 0);
Func<mlong, monoid, monoid> apply = (z, p) => (p.Item1 + z * p.Item2, p.Item2);
var st = new SegTreeII<monoid, mlong>(N, dot, dotidentity, (x, y) => x + y, 0, apply);
monoid[] ini = new monoid[N];
for(int i = 0; i < N; i++) {
int node = hld.HLD_Node[i];
ini[i] = ((mlong)S[node], (mlong)C[node]);
}
st.Init(ini);
var sb = new StringBuilder();
foreach(var query in Query) {
switch (query[0]) {
case 0: {
int x = query[1] - 1;
int y = query[2] - 1;
mlong z = query[3];
var path = hld.GetPath(x, y);
foreach(var uv in path) {
int ui = uv[0], vi = uv[1];
st.RangeOperation(ui, vi + 1, z);
}
} break;
case 1: {
int x = query[1] - 1;
int y = query[2] - 1;
var path = hld.GetPath(x, y);
mlong tot = 0;
foreach (var uv in path) {
int ui = uv[0], vi = uv[1];
mlong sum = st.Query(ui, vi + 1).Item1;
tot += sum;
}
sb.AppendLine(tot.ToString());
}
break;
}
}
Console.Write(sb.ToString());
}
int N;
long[] S;
long[] C;
int[] A, B;
int Q;
int[][] Query;
public Sol() {
N = ri();
S = rla();
C = rla();
A = new int[N - 1];
B = new int[N - 1];
for(int i = 0; i < N - 1; i++) {
var d = ria();
A[i] = d[0] - 1;
B[i] = d[1] - 1;
}
Q = ri();
Query = new int[Q][];
for (int i = 0; i < Q; i++) Query[i] = ria();
}
static String rs() { return Console.ReadLine(); }
static int ri() { return int.Parse(Console.ReadLine()); }
static long rl() { return long.Parse(Console.ReadLine()); }
static double rd() { return double.Parse(Console.ReadLine()); }
static String[] rsa(char sep = ' ') { return Console.ReadLine().Split(sep); }
static int[] ria(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => int.Parse(e)); }
static long[] rla(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => long.Parse(e)); }
static double[] rda(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Split(sep), e => double.Parse(e)); }
static T[] mka<T>(int n, T ini) { T[] ret = new T[n]; for (int i = 0; i < n; i++) ret[i] = ini; return ret; }
static T[][] mka<T>(int n, int m, T ini) { T[][] ret = new T[n][]; for (int i = 0; i < n; i++) ret[i] = mka(m, ini); return ret; }
static T[][][] mka<T>(int n, int m, int l, T ini) { T[][][] ret = new T[n][][]; for (int i = 0; i < n; i++) ret[i] = mka(m, l, ini); return ret; }
static T[][][][] mka<T>(int n, int m, int l, int k, T ini) { T[][][][] ret = new T[n][][][]; for (int i = 0; i < n; i++) ret[i] = mka(m, l, k, ini); return ret; }
static T[] mka<T>(int n) where T : new() { T[] ret = new T[n]; for (int i = 0; i < n; i++) ret[i] = new T(); return ret; }
static T[][] mka<T>(int n, int m) where T : new() { T[][] ret = new T[n][]; for (int i = 0; i < n; i++) ret[i] = mka<T>(m); return ret; }
static T[][][] mka<T>(int n, int m, int l) where T : new() { T[][][] ret = new T[n][][]; for (int i = 0; i < n; i++) ret[i] = mka<T>(m, l); return ret; }
static T[][][][] mka<T>(int n, int m, int l, int k) where T : new() { T[][][][] ret = new T[n][][][]; for (int i = 0; i < n; i++) ret[i] = mka<T>(m, l, k); return ret; }
class SegTreeII<S, T> {
// field
S[] Data;
S DotIdentityElement;
Func<S, S, S> Dot;
T[] Operator;
Func<T, T, T> Compose = null;
T ComposeIdentityElement;
Func<T, S, S> Apply = null;
public int N; // base space size
int n; // total size (pow of 2)
int height;
//constructor
public SegTreeII(int n_, Func<S, S, S> dot_, S dotIdentityElement_, Func<T, T, T> compose_, T composeIdentityElement_, Func<T, S, S> apply_) {
N = n_;
n = 1;
height = 1;
while (n < n_ + 1) { n *= 2; height++; }
DotIdentityElement = dotIdentityElement_;
Dot = dot_;
Data = new S[2 * n];
for (int i = 0; i < 2 * n; i++) Data[i] = DotIdentityElement;
ComposeIdentityElement = composeIdentityElement_;
Compose = compose_;
Operator = new T[2 * n];
for (int i = 0; i < 2 * n; i++) Operator[i] = ComposeIdentityElement;
Apply = apply_;
}
public void RangeOperation(int a, int b, T t) {
int ta = a + n;
for (int i = height - 1; i > 0; i--) Propagate(ta >> i);
int tb = b - 1 + n;
for (int i = height - 1; i > 0; i--) Propagate(tb >> i);
ta = a + n;
tb = b + n;
while (tb > ta) {
if ((ta & 1) == 1) { Operator[ta] = Compose(Operator[ta], t); ta++; }
if ((tb & 1) == 1) { tb--; Operator[tb] = Compose(Operator[tb], t); }
ta >>= 1; tb >>= 1;
}
ta = a + n;
tb = b - 1 + n;
int l, r;
for (int i = 0; i < height - 1; i++) {
l = (ta >> 1) << 1; r = l ^ 1;
Data[ta >> 1] = Dot(Apply(Operator[l], Data[l]), Apply(Operator[r], Data[r]));
l = (tb >> 1) << 1; r = l ^ 1;
Data[tb >> 1] = Dot(Apply(Operator[l], Data[l]), Apply(Operator[r], Data[r]));
ta >>= 1;
tb >>= 1;
}
}
public void Propagate(int k) {
if (k * 2 < 2 * n) { // cared non-contradiction call??
Data[k] = Apply(Operator[k], Data[k]);
Operator[k * 2] = Compose(Operator[k * 2], Operator[k]);
Operator[k * 2 + 1] = Compose(Operator[k * 2 + 1], Operator[k]);
Operator[k] = ComposeIdentityElement;
}
}
public S Query(int a, int b) {
// Fold_left Dot [a, b)
int ta = a + n;
for (int i = height - 1; i > 0; i--) Propagate(ta >> i);
int tb = b - 1 + n;
for (int i = height - 1; i > 0; i--) Propagate(tb >> i);
a += n;
b += n;
S vl = DotIdentityElement;
S vr = DotIdentityElement;
while (b > a) {
if ((a & 1) == 1) { vl = Dot(vl, Apply(Operator[a], Data[a])); a++; }
if ((b & 1) == 1) { b--; vr = Dot(Apply(Operator[b], Data[b]), vr); }
a >>= 1; b >>= 1;
}
return Dot(vl, vr);
}
public S QueryAll {
get { return Apply(Operator[0], Data[0]); }
}
public S At(int idx) {
return Query(idx, idx + 1);
}
public void UniqInit(S v) {
for (int i = 0 + n; i < N + n; i++) Data[i] = v;
for (int i = n - 1; i >= 1; i--) {
Data[i] = Dot(Data[i * 2], Data[i * 2 + 1]);
}
}
public void Init(S[] a) {
for (int i = 0; i < a.Length; i++) Data[i + n] = a[i];
for (int i = n - 1; i >= 0; i--) {
Data[i] = Dot(Data[i * 2], Data[i * 2 + 1]);
}
}
public void Dump<U>(U[] arr, Func<U, String> str = null) {
Console.WriteLine();
int h = 0;
int cnt = 0;
for (int i = 1; i < arr.Length; i++) {
Console.Write("{0} ", str == null ? arr[i].ToString() : str(arr[i]));
cnt++;
if (cnt == 1 << h) {
cnt = 0;
h++;
Console.WriteLine();
}
}
}
public void DumpData(Func<S, String> str = null) { Dump(this.Data, str); }
public void DumpOperator(Func<T, String> str = null) { Dump(this.Operator, str); }
public void DumpPair(Func<S, String> strData = null, Func<T, String> strOp = null) {
Func<Tuple<S, T>, String> str = p => String.Format("[{0}, {1}]", strData == null ? p.Item1.ToString() : strData(p.Item1), strOp == null ? p.Item2.ToString() : strOp(p.Item2));
Dump(this.Data.Zip(this.Operator, (s, t) => new Tuple<S, T>(s, t)).ToArray(), str);
}
}
}
struct mlong {
const long mod = (long)1e9 + 7;
long V;
public mlong(long _v = 0) {
V = _v;
}
public static mlong operator +(mlong a, mlong b) {
var v0 = a.V + b.V; if (v0 >= mod) v0 -= mod;
return new mlong(v0);
}
public static mlong operator -(mlong a, mlong b) {
var v0 = mod + a.V - b.V; if (v0 >= mod) v0 -= mod;
return new mlong(v0);
}
public static mlong operator -(mlong b) {
var v0 = mod - b.V; if (v0 >= mod) v0 -= mod;
return new mlong(v0);
}
public static mlong operator *(mlong a, mlong b) {
var v0 = a.V * b.V; if (v0 >= mod) v0 %= mod;
return new mlong(v0);
}
public static mlong operator /(mlong a, mlong b) {
var v0 = a.V * inv(b.V).V; if (v0 >= mod) v0 %= mod;
return new mlong(v0);
}
public static mlong inv(long x) {
long a = 0, b = 0, c = 0;
ExtGCD(x, mod, ref a, ref b, ref c);
return (mlong)((a + mod) % mod);
}
public static void ExtGCD(long x, long y, ref long a, ref long b, ref long c) {
long r0 = x; long r1 = y;
long a0 = 1; long a1 = 0;
long b0 = 0; long b1 = 1;
long q1, r2, a2, b2;
while (r1 > 0) {
q1 = r0 / r1;
r2 = r0 % r1;
a2 = a0 - q1 * a1;
b2 = b0 - q1 * b1;
r0 = r1; r1 = r2;
a0 = a1; a1 = a2;
b0 = b1; b1 = b2;
}
c = r0;
a = a0;
b = b0;
}
public static mlong ModPow(mlong a, long k) {
if (k == 0) return (mlong)1;
if (a == 0) return (mlong)0;
mlong x = a;
mlong ret = 1;
while (k > 0) {
if (k % 2 == 1) ret *= x;
x *= x;
k >>= 1;
}
return ret;
}
public static bool operator ==(mlong a, mlong b) {
return a.Equals(b);
}
public static bool operator !=(mlong a, mlong b) {
return !(a == b);
}
public override bool Equals(System.Object obj) {
if (obj == null) return false;
mlong p = (mlong)obj;
if ((System.Object)p == null) return false;
return p.V == V;
}
public override int GetHashCode() {
return V.GetHashCode();
}
public static implicit operator mlong(long n) {
long v = n % mod; if (v < 0) v += mod;
return new mlong(v);
}
public static implicit operator mlong(int n) {
long v = n % mod; if (v < 0) v += mod;
return new mlong(v);
}
public static explicit operator long(mlong n) {
return n.V;
}
public override String ToString() {
return V.ToString();
}
}
namespace TreeDecompostion {
class HeavyLightDecompotion {
// org
public int N { get; private set; }
public List<int>[] E { get; private set; }
public int Root { get; private set; }
public int[] Ccnt { get; private set; }
public int[] Depth { get; private set; }
public int[] Parent { get; private set; }
public int[] HLD_Node { get; private set; } // arrange heavynode in preorder
public int[] HLD_Compo { get; private set; } // heavy component index
public int[] HLD_Head { get; private set; } // head position in HLD_Node
public int[] HLD_NodeIdx { get; private set; } // node x at HLD_NodeIdx[x] in HLD_Node
public HeavyLightDecompotion(int n, List<int>[] e, int root) {
N = n;
E = new List<int>[N];
for (int i = 0; i < N; i++) E[i] = new List<int>(e[i]);
Root = root;
}
public void Build(int root = -1) {
if (root != -1) Root = root;
// initialize
Ccnt = new int[N];
Depth = new int[N];
for (int i = 0; i < N; i++) Depth[i] = -1;
Parent = new int[N];
for (int i = 0; i < N; i++) Parent[i] = -1;
Parent[Root] = -1;
HLD_Compo = new int[N];
HLD_Node = new int[N];
// count children
dfs_size();
// composition
dfs_HLD();
HLD_Head = new int[N];
for (int i = 0; i < N; i++) {
if (i == 0 || HLD_Compo[i] != HLD_Compo[i - 1]) {
HLD_Head[i] = i;
} else {
HLD_Head[i] = HLD_Head[i - 1];
}
}
HLD_NodeIdx = new int[N];
for (int i = 0; i < N; i++) {
HLD_NodeIdx[HLD_Node[i]] = i;
}
}
public List<int[]> GetPath(int u, int v) {
// returns List of intervals in HLD_Node
var ret = new List<int[]>();
int ui = HLD_NodeIdx[u];
int vi = HLD_NodeIdx[v];
while (HLD_Compo[ui] != HLD_Compo[vi]) {
int hu = HLD_Node[HLD_Head[ui]];
int hv = HLD_Node[HLD_Head[vi]];
if (Depth[hu] >= Depth[hv]) {
ret.Add(new int[] { HLD_Head[ui], ui });
ui = HLD_NodeIdx[Parent[hu]];
} else {
ret.Add(new int[] { HLD_Head[vi], vi });
vi = HLD_NodeIdx[Parent[hv]];
}
}
if (ui > vi) {
var tmp = ui; ui = vi; vi = tmp;
}
ret.Add(new int[] { ui, vi });
return ret;
}
public int LCA(int u, int v) {
int ui = HLD_NodeIdx[u];
int vi = HLD_NodeIdx[v];
while (HLD_Compo[ui] != HLD_Compo[vi]) {
int hu = HLD_Node[HLD_Head[ui]];
int hv = HLD_Node[HLD_Head[vi]];
if (Depth[hu] >= Depth[hv]) {
ui = HLD_NodeIdx[Parent[hu]];
} else {
vi = HLD_NodeIdx[Parent[hv]];
}
}
if (ui > vi) {
var tmp = ui; ui = vi; vi = tmp;
}
return HLD_Node[ui];
}
int dfs_size() {
int[] freq = new int[N];
var stk = new Stack<int>();
stk.Push(Root);
while (stk.Count > 0) {
var now = stk.Pop();
freq[now]++;
if (freq[now] == 1) { // pre order
Ccnt[now] = 1;
stk.Push(now);
foreach (var nxt in E[now]) {
if (freq[nxt] == 0) {
Depth[nxt] = Depth[now] + 1;
Parent[nxt] = now;
stk.Push(nxt);
}
}
} else if (freq[now] == 2) { // post order
if (Parent[now] != -1) Ccnt[Parent[now]] += Ccnt[now];
}
}
return Ccnt[Root];
}
void dfs_HLD() {
var stk = new Stack<(int, int)>();
stk.Push((Root, 0));
int idx = 0;
int tot_compo = 0;
while (stk.Count > 0) {
var (now, compo) = stk.Pop();
HLD_Node[idx] = now;
HLD_Compo[idx] = compo;
idx++;
int heavynode = -1;
foreach (var nxt in E[now]) {
if (nxt == Parent[now]) continue;
if (heavynode == -1 || Ccnt[nxt] > Ccnt[heavynode]) {
heavynode = nxt;
}
}
if (heavynode == -1) continue;
// for popping first heavy then others follow
foreach (var nxt in E[now]) {
if (nxt == Parent[now] || nxt == heavynode) continue;
tot_compo++;
stk.Push((nxt, tot_compo));
}
stk.Push((heavynode, compo));
}
}
void dfs_HLD_rec(int now, int idx, ref int compo) {
HLD_Node[idx] = now;
HLD_Compo[idx] = compo;
int heavynode = -1;
foreach (var nxt in E[now]) {
if (Depth[nxt] < Depth[now]) continue;
if (heavynode == -1 || Ccnt[nxt] > Ccnt[heavynode]) {
heavynode = nxt;
}
}
if (heavynode == -1) return;
// first heavy then others follow
dfs_HLD_rec(heavynode, ++idx, ref compo);
foreach (var nxt in E[now]) {
if (Depth[nxt] < Depth[now] || nxt == heavynode) continue;
++compo;
dfs_HLD_rec(nxt, ++idx, ref compo);
}
}
int dfs_size_rec(int now, int prev) {
Ccnt[now] = 1;
foreach (var nxt in E[now]) {
if (Depth[nxt] == -1) {
Depth[nxt] = Depth[now] + 1;
Ccnt[now] += dfs_size_rec(nxt, now);
}
}
return Ccnt[now];
}
}
}
}