#867254 (C#(csc)) No.235 めぐるはめぐる (5)

• 問題: No.235 めぐるはめぐる (5)
• ユーザー: kuuso1
• 提出日時: 2023-05-07 17:25:00
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 9,325 ms / 10,000 ms
• コード長: 16,125 bytes
• コンパイル時間: 2,907 ms
• コンパイル使用メモリ: 116,352 KB
• 実行使用メモリ: 111,652 KB
• 最終ジャッジ日時: 2024-11-24 16:40:46
• 合計ジャッジ時間: 35,877 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	9,325 ms; 111,652 KB
testcase_01	AC	5,764 ms; 103,020 KB
testcase_02	AC	8,768 ms; 101,768 KB

コンパイルメッセージ

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;
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.GetPathTuple(x, y);
							foreach(var (ui,vi) 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.GetPathTuple(x, y);
							mlong tot = 0;
							foreach (var (ui,vi) 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 List<(int,int)> GetPathTuple(int u, int v) {
				// returns List of intervals in HLD_Node

				var ret = new List<(int,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((HLD_Head[ui], ui));
						ui = HLD_NodeIdx[Parent[hu]];
					} else {
						ret.Add((HLD_Head[vi], vi));
						vi = HLD_NodeIdx[Parent[hv]];
					}
				}
				if (ui > vi) {
					var tmp = ui; ui = vi; vi = tmp;
				}
				ret.Add((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];
			}


		}


	}
}