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

提出ソース

結果

問題	No.235 めぐるはめぐる (5)
ユーザー	kuuso1
提出日時	2016-07-18 22:45:18
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	1,846 ms / 10,000 ms
コード長	11,190 bytes
コンパイル時間	4,466 ms
コンパイル使用メモリ	111,360 KB
実行使用メモリ	159,544 KB
最終ジャッジ日時	2024-10-15 17:06:47
合計ジャッジ時間	10,907 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,846 ms 132,052 KB
testcase_01	AC	1,406 ms 159,544 KB
testcase_02	AC	1,722 ms 139,552 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

class TEST{
	static void Main(){
		Sol mySol = new Sol();
		mySol.Solve();
	}
}

class Sol{	
	
	public void Solve(){
		
		
		root = 0;
		lca_init();
		nNode = new int[N];
		dfs_cnt();
		EHeavy = new int[N];
		for(int i=0;i<N;i++) EHeavy[i] = -1;
		Compo = new int[N];
		Idx = new int[N];
		HLDec = new List<List<int>>();
		dfs_HLDec();
		
		int NHL=HLDec.Count;
		
		long[][] sVal = new long[NHL][];
		long[][] sSum = new long[NHL][];
		for(int i=0;i<NHL;i++){
			sVal[i] = new long[HLDec[i].Count];
			sSum[i] = new long[HLDec[i].Count+1];
		}
		for(int i=0;i<N;i++){
			sVal[Compo[i]][Idx[i]] = S[i];
		}
		for(int i=0;i<NHL;i++){
			sSum[i][1] = sVal[i][0];
			for(int j=1;j<sVal[i].Length;j++){
				sSum[i][j+1] = sSum[i][j] + sVal[i][j];
				if(sSum[i][j+1] >= mod) sSum[i][j+1] %= mod;
			}
		}
		
		SegTree[] ST=new SegTree[NHL];
		for(int i=0;i<NHL;i++){
			ST[i] = new SegTree(HLDec[i].Count);
		}
		
		for(int i=0;i<N;i++){
			var st = ST[Compo[i]];
			int pos = Idx[i];
			st.Update(pos, C[i]);
		}
		
		StringBuilder sb=new StringBuilder();
		
		foreach(var qr in Query){
			if(qr[0] == 0){
				int a = qr[1];
				int b = qr[2];
				long z = qr[3];
				int c = lca(a,b);
				
				while(Compo[a] != Compo[c]){
					ST[Compo[a]].AddRange(0,Idx[a]+1,z,0,0,ST[Compo[a]].n);
					a = HLDec[Compo[a]][0];
					a = parent[0][a];
				}
				while(Compo[b] != Compo[c]){
					ST[Compo[b]].AddRange(0,Idx[b]+1,z,0,0,ST[Compo[b]].n);
					b = HLDec[Compo[b]][0];
					b = parent[0][b];
				}
				
				if(Idx[b] < Idx[a]){
					int tmp = a; a = b; b = tmp;
				}
				
				ST[Compo[c]].AddRange(Idx[a],Idx[b]+1,z,0,0,ST[Compo[c]].n);
			}
			if(qr[0] == 1){		
				int a = qr[1];
				int b = qr[2];
				int c = lca(a,b);
				long sum = 0;
				
				while(Compo[a] != Compo[c]){
					sum += ST[Compo[a]].QuerySum(0,Idx[a]+1);
					if(sum >= mod) sum -= mod;
					sum += sSum[Compo[a]][Idx[a]+1] - sSum[Compo[a]][0] + mod;
					while(sum >= mod) sum -= mod;
					
					a = HLDec[Compo[a]][0];
					a = parent[0][a];
				}
				while(Compo[b] != Compo[c]){
					sum += ST[Compo[b]].QuerySum(0,Idx[b]+1);
					if(sum >= mod) sum -= mod;
					sum += sSum[Compo[b]][Idx[b]+1] - sSum[Compo[b]][0] + mod;
					while(sum >= mod) sum -= mod;
					b = HLDec[Compo[b]][0];
					b = parent[0][b];
				}
				
				if(Idx[b] < Idx[a]){
					int tmp = a; a = b; b = tmp;
				}
				
				sum += ST[Compo[c]].QuerySum(Idx[a],Idx[b]+1);
				if(sum >= mod) sum -= mod;
				sum += sSum[Compo[c]][Idx[b]+1] - sSum[Compo[c]][Idx[a]] + mod;
				while(sum >= mod) sum -= mod;
				
				sb.AppendLine(sum.ToString());
			}
		}
		Console.Write(sb.ToString());
	}
	
	
	
	
	int N;
	long[] S,C;
	List<int>[] E;
	int Q;
	List<int>[] Query;
	static long mod = (long)1e9+7;
	
	int[][] parent;
	int[] depth;
	static int lmax=24;
	int root;
	
	int[] nNode;
	int[] EHeavy;
	int[] Compo;
	int[] Idx;
	//int cmp;
	List<List<int>> HLDec;
	
	struct Triple{
		public int node,compo,idx;
		public Triple(int n_,int c_,int i_){
			node=n_;compo=c_;idx=i_;
		}
	}
	void dfs_HLDec(){
//Console.WriteLine("now={0},cmp={1},idx={2}",now,cmp,idx);
		
		Stack<Triple> Stk=new Stack<Triple>();
		Stk.Push(new Triple(root,0,0));
		Compo[0]=0;
		Idx[0]=0;
		HLDec.Add(new List<int>());
		HLDec[0].Add(0);
		//cmp=1;
		
		while(Stk.Count>0){
			var p=Stk.Pop();
			int now=p.node;
			int c=p.compo;
			int idx=p.idx;
//Console.WriteLine(now+" "+c+" "+idx);			
			int max=0;int trgt=-1;
			foreach(var nxt in E[now]){
				if(nxt==parent[0][now])continue;
				if(max<nNode[nxt]){
					trgt=nxt;
					max=nNode[nxt];
				}
			}
			if(trgt!=-1){
				EHeavy[now]=trgt;
			}
			foreach(var nxt in E[now]){
				if(nxt!=parent[0][now] && nxt!=EHeavy[now]){
					HLDec.Add(new List<int>());
					Compo[nxt]=HLDec.Count-1;
					Idx[nxt]=0;
					HLDec[Compo[nxt]].Add(nxt);
					Stk.Push(new Triple(nxt,Compo[nxt],0));
				}
				if(nxt==EHeavy[now]){
					Compo[nxt]=c;
					Idx[nxt]=idx+1;
					HLDec[Compo[nxt]].Add(nxt);
					Stk.Push(new Triple(nxt,c,idx+1));
				}
			}
		}
	}		
	
	class Pair{
		public int node,depth;
		public Pair(int n_,int d_){
			node=n_;depth=d_;
		}
	}
	void dfs_cnt(){
		Pair[] P=new Pair[N];
		for(int i=0;i<N;i++){
			P[i]=new Pair(i,depth[i]);
		}
		Array.Sort(P,(x,y)=>x.depth>y.depth?-1:x.depth<y.depth?1:0);
		for(int i=0;i<N;i++){
			nNode[P[i].node]++;
			if(P[i].node!=root)nNode[parent[0][P[i].node]]+=nNode[P[i].node];
		}
	}
	
	void lca_init(){
		parent=new int[lmax][];
		for(int i=0;i<lmax;i++){
			parent[i]=new int[N];
		}
		depth=new int[N];
		
		//root=0;
		//dfs(root,-1,0);//dfs
		bfs(root,0);//bfs
		
		for(int i=0;i<lmax-1;i++){
			for(int j=0;j<N;j++){
				if(parent[i][j]<0){
					parent[i+1][j]=-1;
				}else{
					parent[i+1][j]=parent[i][parent[i][j]];
				}
			}
		}
		
	}
	
	int lca(int u,int v){
		if(depth[u]>depth[v])return lca(v,u);
		for(int i=0;i<lmax;i++){
			if( (((depth[v]-depth[u])>>i)&1) >0 ){
				v=parent[i][v];
			}
		}
		if(u==v)return u;
		for(int i=lmax-1;i>=0;i--){
			if(parent[i][u]!=parent[i][v]){
				u=parent[i][u];
				v=parent[i][v];
			}
		}
		return parent[0][u];
	}
	
	void bfs(int strt,int dep_strt){
		Queue<int> Q=new Queue<int>();
		parent[0][strt]=-1;depth[strt]=0;
		Q.Enqueue(strt);
		while(Q.Count>0){
			int now=Q.Dequeue();
			int par=parent[0][now];
			foreach(int v in E[now]){
				if(v!=par){
					parent[0][v]=now;depth[v]=depth[now]+1;
					Q.Enqueue(v);
				}
			}
		}
	}
	
	
	public Sol(){
		using (var r = new FastIn(100000)){
			N = r.ReadInt();
			S = new long[N];
			for(int i=0;i<N;i++){
				S[i] = r.ReadLong();
			}
			C = new long[N];
			for(int i=0;i<N;i++){
				C[i] = r.ReadLong();
			}
			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++){
				int a = r.ReadInt()-1;
				int b = r.ReadInt()-1;
				E[a].Add(b);
				E[b].Add(a);
			}
			Q = r.ReadInt();
			Query = new List<int>[Q];
			for(int i=0;i<Q;i++){
				Query[i] = new List<int>(4);
				Query[i].Add(r.ReadInt());
				Query[i].Add(r.ReadInt()-1);
				Query[i].Add(r.ReadInt()-1);
				if(Query[i][0] == 0){
					Query[i].Add(r.ReadInt());
				}
			}
		}
	}
	
	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));}
}


class SegTree{
	//segment Tree 
	// 0-origin
	long[] Data;	//
	long[] Lazy;
	long[] Coef;
	long Inf;	//largeNumber
	int N;		//size 
	public int n;		//size (2)
	static long mod = (long)1e9+7;
	
	public SegTree(int n_){
		N=n_;Inf=0;
		n=1;
		while(n<n_)n*=2;
		Data=new long[2*n-1];
		for(int i=0;i<2*n-1;i++)Data[i]=0;
		Lazy=new long[2*n-1];
		for(int i=0;i<2*n-1;i++)Lazy[i]=0;
		Coef=new long[2*n-1];
		for(int i=0;i<2*n-1;i++)Coef[i]=0;
	}
	
	//k-a(Min
	//	   0
	//	 1   2
	//	3 4 5 6
	public void Update(int k,long c){
		k+=n-1;	//n-1
		Coef[k] = c;
		while(k>0){
			k=(k-1)/2;
			Coef[k] = Coef[k*2+1] + Coef[k*2+2];
			if(Coef[k] >= mod) Coef[k] -= mod;
		}
	}
	
	//RMQ;
	//	[a,b) Max
	//	3	k,l,rk- [l,r) 
	//	 Query(a,b,0,0,n) 
	public long Query(int a,int b,int k,int l,int r){
		// [a,b)  [l,r) =Inf
		if(r<=a || b<=l) return Inf;
		// [a,b)  [l,r) Data[k] 
		if(a<=l && r<=b)return Data[k];
		// 
		long vl=Query(a,b,k*2+1,l,(l+r)/2);
		long vr=Query(a,b,k*2+2,(l+r)/2,r);
		return vl + vr;
	}
	
	public long QuerySum(int a,int b){
		QuerySumRet = 0;
		
		QueryWithLazy(a,b,0,0,n);
		
		return QuerySumRet;
	}
	long QuerySumRet;
	
	
	public long QueryWithLazy(int a,int b,int k,int l,int r){
//Console.WriteLine("in query:a={0},b={1},k={2},l={3},r={4}",a,b,k,l,r);
		// [a,b)  [l,r) =Inf
		if(r<=a || b<=l) return Inf;
		// [a,b)  [l,r) Data[k] 
		if(a<=l && r<=b){
			long inc = Coef[k] * Lazy[k] + Data[k];
			if(inc >= mod) inc %= mod;
			QuerySumRet += inc;
			if(QuerySumRet >= mod) QuerySumRet -= mod;
			return Coef[k];
		}
		 
		long cl=QueryWithLazy(a,b,k*2+1,l,(l+r)/2);
		long cr=QueryWithLazy(a,b,k*2+2,(l+r)/2,r);
		long clr = cl + cr;
		long ret = Lazy[k] * clr;
		if(ret >= mod) ret %= mod;
		QuerySumRet += ret;
		if(QuerySumRet >= mod) QuerySumRet -= mod;
		return clr;
	}
	public void AddRange(int a,int b,long val,int k,int l,int r){
		// [a,b)  [l,r) Data[k]+val
		if(r<=a || b<=l) return;
		if(a<=l && r<=b){
			Lazy[k] += val;
			if(Lazy[k] >= mod) Lazy[k] -= mod;
			long inc = val * Coef[k];
			if(inc >= mod) inc %= mod;
			while(k>0){
				k=(k-1)/2;
				Data[k] += inc;
				if(Data[k] >= mod) Data[k] -= mod;
			}
			return;
		}
		AddRange(a,b,val,k*2+1,l,(l+r)/2);
		AddRange(a,b,val,k*2+2,(l+r)/2,r);
	}
	
	public void UniqInit(int val){
		for(int i=0+n-1;i<N+n-1;i++)Data[i]=val;
		int l=n-1;int r=N+n-1-1;
		while(l>0){
			l=(l-1)/2;r=(r-1)/2;
			for(int i=l;i<=r;i++)Data[i]=val;
		}
	}
	
	public void Dump(){
		Console.WriteLine();
		int h=0;
		int cnt=0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",Data[i]);
			cnt++;
			if(cnt==1<<h){
				cnt=0;
				h++;
				Console.WriteLine();
			}
		}
		Console.WriteLine();
		h=0;
		cnt=0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",Lazy[i]);
			cnt++;
			if(cnt==1<<h){
				cnt=0;
				h++;
				Console.WriteLine();
			}
		}
	}
}


class FastIn:IDisposable {
	int Size;
	byte[] Mem;
	int ptr;
	int rsize;
	bool unfinished;
	Stream stdin;
	void Init(int n) {
		Size = n;
		Mem = new byte[Size];
		rsize=(stdin=Console.OpenStandardInput()).Read(Mem, 0, Size);
		ptr = 0;
		unfinished=(rsize == Size);
	}
	void Next() {
		if (unfinished == false) return;
		rsize=stdin.Read(Mem, 0, Size);
		ptr = 0;
		unfinished = (rsize == Size);
	}
	
	~FastIn(){
		stdin.Dispose();
	}
	void IDisposable.Dispose(){
		stdin.Dispose();
	}
	public void Dispose(){
		stdin.Dispose();
	}
	
	public FastIn() {
		Init(100000);
	}
	public FastIn(int n) {
		Init(n);
	}
	public int ReadInt() {
		int ret = 0;
		int sig = 1;
		while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
			if(ret==0 && Mem[ptr] == '-'){
				sig *= -1; ptr++; continue;
			}
			ret = ret * 10 + Mem[ptr++] - '0';
			if (ptr == Size) Next();
		}
		while (ptr < rsize && (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r') ) {
			ptr++;
			if (ptr == Size) Next();
		}
		return ret*sig;
	}
	public long ReadLong() {
		long ret = 0;
		long sig = 1;
		while (ptr < rsize && Mem[ptr] != ' ' && Mem[ptr] != '\n' && Mem[ptr] != '\r' ) {
			if(ret==0 && Mem[ptr] == '-'){
				sig *= -1; ptr++; continue;
			}
			ret = ret * 10 + Mem[ptr++] - '0';
			if (ptr == Size) Next();
		}
		while (ptr < rsize &&  (Mem[ptr] == ' ' || Mem[ptr] == '\n' || Mem[ptr] == '\r')  ) {
			ptr++;
			if (ptr == Size) Next();
		}
		return ret*sig;
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード