結果

問題 No.650 行列木クエリ
コンテスト
ユーザー kuuso1
提出日時 2018-02-10 00:03:51
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 498 ms / 2,000 ms
コード長 8,036 bytes
コンパイル時間 1,255 ms
コンパイル使用メモリ 119,492 KB
実行使用メモリ 80,964 KB
最終ジャッジ日時 2024-10-09 09:04:44
合計ジャッジ時間 4,699 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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[] e2n = new int[N-1];
		for(int i=0;i<N-1;i++){
			e2n[i] = depth[A[i]] < depth[B[i]] ? B[i] : A[i];
		}
		
		
		
//foreach(var mem in HLDec) Console.WriteLine(String.Join(" ",mem));
		
		int NHL=HLDec.Count;
		SegTree<Mat2x2>[] ST = new SegTree<Mat2x2>[NHL];
		for(int i=0;i<NHL;i++){
			ST[i]=new SegTree<Mat2x2>(HLDec[i].Count, new Mat2x2(1, 0, 0, 1), (a, b) => a * b);
			ST[i].UniqInit(new Mat2x2(1, 0, 0, 1));
//ST[i].Dump();
		}
		
		for(int q=0;q<Q;q++){
			String[] ss = Qs[q];
			switch(ss[0][0]){
				
				case 'x': {
					int t = int.Parse(ss[1]);
					int nd = e2n[t];
					long a = long.Parse(ss[2]);
					long b = long.Parse(ss[3]);
					long c = long.Parse(ss[4]);
					long d = long.Parse(ss[5]);
					var  m = new Mat2x2(a, b, c, d);
					ST[Compo[nd]].Update(Idx[nd], m);
					
				} break;
				case 'g': {
					int par = int.Parse(ss[1]);
					int chi = int.Parse(ss[2]);
					
					var m = Mat2x2.Unit;
					while(Compo[chi] != Compo[par]){
						var pr = ST[Compo[chi]].Query(0, Idx[chi] + 1);
						m = pr * m;
						chi = HLDec[Compo[chi]][0];
						chi = parent[0][chi];
					}
					
					m = ST[Compo[chi]].Query(Idx[par] + 1, Idx[chi] + 1) * m;
					Console.WriteLine(m);
					
					
				} break;
				
			}
		}
	}
	
	int[][] parent;
	int[] depth;
	static int lmax=24;
	int root;
	
	int[] nNode;
	int[] EHeavy;
	int[] Compo;
	int[] Idx;
	//int cmp;
	
	int N;
	List<int>[] E;
	int[] A,B;
	
	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);
				}
			}
		}
	}
	
	
	
	
	int Q;
	String[][] Qs;
	public Sol(){
		
		N = ri();
		E = new List<int>[N];
		for(int i=0;i<N;i++) E[i] = new List<int>();
		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]; B[i] = d[1];
			E[d[0]].Add(d[1]);
			E[d[1]].Add(d[0]);
		}
		
		Q = ri();
		Qs = new String[Q][];
		for(int i=0;i<Q;i++) Qs[i] = rsa();
	}

	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));}
}



struct Mat2x2{
	long[] m;
	const long mod = (long) 1e9 + 7;
	
	public static Mat2x2 Unit = new Mat2x2(1,0,0,1);
	
	public long this[int r, int c]{
		get{ return m[(r<<1) + c]; }
		set{ m[(r<<1) + c] = value; }
	}
/*	
	public Mat2x2(){
		m = new long[4];
	}
*/
	public Mat2x2(long a = 0, long b = 0, long c = 0, long d = 0){
		m = new long[]{a, b, c, d};
	}
	
	public static Mat2x2 operator * (Mat2x2 ma, Mat2x2 mb){
		var ret = new Mat2x2(0, 0, 0, 0);
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				for(int k=0;k<2;k++){
					ret[i, j] += ma[i, k] * mb[k, j];
					ret[i, j] %= mod;
				}
			}
		}
		return ret;
	}
	
	public static long[] operator * (Mat2x2 ma, long[] v){
		var ret = new long[2];
		ret[0] = ma[0, 0] * v[0] + ma[0, 1] * v[1];// ret[0] %= mod;
		ret[1] = ma[1, 0] * v[0] + ma[1, 1] * v[1];// ret[1] %= mod;
		return ret;
	}
	
	public override String ToString(){
		return String.Join(" ",m);
	}
	
}


class SegTree<T>{
	//segment Tree 
	// 0-origin
	T[] Data;	
	T Ini;
	Func<T,T,T> Op;
	int N;
	int n;
	
	//コンストラクタ
	public SegTree(int n_,T ini_, Func<T,T,T> op_){
		N = n_;
		Ini = ini_;
		n = 1;
		while(n < n_) n *= 2;
		Data = new T[2*n - 1];
		for(int i=0;i<2*n-1;i++) Data[i] = Ini;
		Op = op_;
	}
	
	//k-番目の値をaに変更
	//	   0
	//	 1   2
	//	3 4 5 6
	public void Update(int k,T a){
		k += n-1;	//上にはn-1個乗る
		Data[k] = a;
		while(k > 0){
			k = (k-1) / 2;
			Data[k] = Op(Data[k*2+1],Data[k*2+2]);
		}
	}
	
	//Query;
	//	[a,b) のOp(...)を返す
	//	後ろ3つの引数は	k,l,r：ヒープのk-ノードが範囲 [l,r) に対応していることを示す
	//	外から呼ぶ時は Query(a,b,0,0,n) の形で呼ぶ
	public T Query(int a, int b){
		return Query(a, b, 0, 0, n);
	}
	
	public T Query(int a,int b,int k,int l,int r){
		// [a,b) ∩ [l,r) =φ　⇒Iniを返す
		if(r<=a || b<=l) return Ini;
		// [a,b) ⊃ [l,r) ⇒Data[k]を返す 
		if(a<=l && r<=b)return Data[k];
		// さもなくば、Op(l,r)を返す
		T vl = Query(a,b,k*2+1,l,(l+r)/2);
		T vr = Query(a,b,k*2+2,(l+r)/2,r);
		return Op(vl, vr);
	}
	
	public void UniqInit(T a){
		for(int i=0;i<N;i++){
			Data[i + (n-1)] = a;
		}
		for(int i=n-2;i>=0;i--){
			Data[i] = Op(Data[i*2+1], Data[i*2+2]);
		}
	}
	public void UniqUnit(T unit){
		for(int i=0;i<n;i++){
			Data[i + (n-1)] = unit;
		}
	}
	
	public T At(int i){
		return Data[i + (n-1)];
	}
	
	public void Dump(){
		Console.WriteLine();
		int h = 0;
		int cnt = 0;
		for(int i=0;i<Data.Length;i++){
			Console.Write("{0} ",Data[i].ToString());
			cnt++;
			if(cnt == 1<<h){
				cnt = 0;
				h++;
				Console.WriteLine();
			}
		}
	}
	
}
0