結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 kuuso1
|
| 提出日時 | 2016-07-18 22:30:43 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,023 bytes |
| コンパイル時間 | 1,301 ms |
| コンパイル使用メモリ | 112,000 KB |
| 実行使用メモリ | 159,536 KB |
| 最終ジャッジ日時 | 2024-10-15 17:05:46 |
| 合計ジャッジ時間 | 8,882 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 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.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];
}
}
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];
if(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];
if(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]];
if(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;
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;
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;
}
}