結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 已经死了
|
| 提出日時 | 2024-06-26 21:32:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 13,863 bytes |
| コンパイル時間 | 311 ms |
| コンパイル使用メモリ | 82,744 KB |
| 実行使用メモリ | 334,368 KB |
| 最終ジャッジ日時 | 2024-06-26 21:32:50 |
| 合計ジャッジ時間 | 23,338 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | TLE * 1 -- * 2 |
ソースコード
import os,sys,random,threading
#sys.exit() 退出程序
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = int(1e20)
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)] # →↘↓↙←↖↑↗
import os,sys,random,threading
#sys.exit() 退出程序
#sys.setrecursionlimit(10**6) #调整栈空间
from random import randint,choice,shuffle
#randint(a,b)从[a,b]范围随机选择一个数
#choice(seq)seq可以是一个列表,元组或字符串,从seq中随机选取一个元素
#shuffle(x)将一个可变的序列x中的元素打乱
from copy import deepcopy
from io import BytesIO,IOBase
from types import GeneratorType
from functools import lru_cache,reduce
#reduce(op,迭代对象)
from bisect import bisect_left,bisect_right
#bisect_left(x) 大于等于x的第一个下标
#bisect_right(x) 大于x的第一个下标
from collections import Counter,defaultdict,deque
from itertools import accumulate,combinations,permutations
#accumulate(a)用a序列生成一个累积迭代器，一般list化前面放个[0]做前缀和用
#combinations(a,k)a序列选k个 组合迭代器
#permutations(a,k)a序列选k个 排列迭代器
from heapq import heapify,heappop,heappush
#heapify将列表转为堆
from typing import Generic,Iterable,Iterator,TypeVar,Union,List
from string import ascii_lowercase,ascii_uppercase,digits
#小写字母，大写字母，十进制数字
from math import ceil,floor,sqrt,pi,factorial,gcd,log,log10,log2,inf
#ceil向上取整，floor向下取整 ，sqrt开方 ，factorial阶乘
from decimal import Decimal,getcontext
#Decimal(s) 实例化Decimal对象,一般使用字符串
#getcontext().prec=100 修改精度
from sys import stdin, stdout, setrecursionlimit
input = lambda: sys.stdin.readline().rstrip("\r\n")
MI = lambda :map(int,input().split())
li = lambda :list(MI())
ii = lambda :int(input())
mod = int(1e9 + 7) #998244353
inf = 1<<60
py = lambda :print("YES")
pn = lambda :print("NO")
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右下左上
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0),(-1, 1)] # →↘↓↙←↖↑↗
class LazySegTree:
"""
v: 初始序列，树叶节点
op: 左右节点之间的合并操作
e: 线段树维护的值的幺元。op(e, x) = op(x, e) = x
mapping: 父结点的懒标记更新子结点的值
composition: 父结点的懒标记更新子结点的懒标记(合并)
id_: 更新操作/懒标记的幺元
"""
def __init__(self,v,op,e,mapping,composition,id_):
self._op = op
self._e = e
self._mapping = mapping
self._composition = composition
self._id = id_
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = (self._n-1).bit_length()
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
self._lz = [self._id] * self._size
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def _update(self, k):
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
def _all_apply(self, k, f):
self._d[k] = self._mapping(f, self._d[k])
if k < self._size:
self._lz[k] = self._composition(f, self._lz[k])
def _push(self, k):
self._all_apply(2 * k, self._lz[k])
self._all_apply(2 * k + 1, self._lz[k])
self._lz[k] = self._id
def set(self, p, x):
#将下标p的位置直接设置成x
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p):
#得到下标为p的位置
p += self._size
for i in range(self._log, 0, -1):
self._push(p >> i)
return self._d[p]
def prod(self, left, right):
#区间查询[left,right]
right+=1
if left == right:
return self._e
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push(right >> i)
sml = self._e
smr = self._e
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self):
#全区间查询
return self._d[1]
def apply(self, left, right, f):
#区间[left,right]更新f
right+=1
if left == right:
return
left += self._size
right += self._size
for i in range(self._log, 0, -1):
if ((left >> i) << i) != left:
self._push(left >> i)
if ((right >> i) << i) != right:
self._push((right - 1) >> i)
l2 = left
r2 = right
while left < right:
if left & 1:
self._all_apply(left, f)
left += 1
if right & 1:
right -= 1
self._all_apply(right, f)
left >>= 1
right >>= 1
left = l2
right = r2
for i in range(1, self._log + 1):
if ((left >> i) << i) != left:
self._update(left >> i)
if ((right >> i) << i) != right:
self._update((right - 1) >> i)
def max_right(self,left,g):
#以left为左端点，找右侧第一个使得g为false的下标
#比如希望区间和大于等于k，那么g就是 return x[0] < k 这里的x[0]就是区间和
if left == self._n:
return self._n
left += self._size
for i in range(self._log, 0, -1):
self._push(left >> i)
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not g(self._op(sm, self._d[left])):
while left < self._size:
self._push(left)
left *= 2
if g(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right, g) -> int:
#以right为右端点，找左侧第一个使得g为false的下标
if right == 0:
return 0
right += self._size
for i in range(self._log, 0, -1):
self._push((right - 1) >> i)
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not g(self._op(self._d[right], sm)):
while right < self._size:
self._push(right)
right = 2 * right + 1
if g(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
class HLD:
def __init__(self, g, root):
#无论是点还是dfn还是dep，都从1开始，默认0是无
n=len(g)
self.g=g
self.fa=[0]*(n+5) #父节点，0表示无父节点
self.size=[1]*(n+5) #子树大小
self.dep=[0]*(n+5) #深度，根深度为1
self.son=[0]*(n+5) #重儿子，0表示无儿子
self.dfn=[0]*(n+5) #dfs序，子树终点的dfs序是dfn[i]+size[i]-1
self.top=[0]*(n+5) #所在重链起点，起点就是自己
self.rank=[0]*(n+5) #dfs序为i的节点编号
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
stk=[[root,0,0]] #node,flag,fa
dep[root]=1
while stk:
u,flag,father=stk.pop()
if flag:
for v in g[u]:
if v!=father:
size[u]+=size[v]
if son[u]==0 or size[v]>size[son[u]]:
son[u]=v
else:
stk.append([u,1,father])
for v in g[u]:
if v!=father:
stk.append([v,0,u])
fa[v]=u
dep[v]=dep[u]+1
stk=[[root,root]]
tot=1
while stk:
u,tops=stk.pop()
dfn[u]=tot
rank[tot]=u
tot+=1
top[u]=tops
if son[u]==0:
continue
for v in g[u]:
if v!=fa[u] and v!=son[u]:
stk.append([v,v])
stk.append([son[u],tops])
def lca(self,u,v): #求u和v的最近公共祖先节点
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
while top[u]!=top[v]:
if dep[top[u]]>dep[top[v]]:
u=fa[top[u]]
else:
v=fa[top[v]]
return v if dep[u]>dep[v] else u
def dis(self,u,v):
dep=self.dep
return dep[u]+dep[v]-2*dep[self.lca(u,v)]
def kth_fa(self,root,k): #求root节点的第k个祖先
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
if k>=dep[root]: #无第k个祖先返回-1
return -1
while True:
u=top[root]
if dfn[root]-k>=dfn[u]:
return rank[dfn[root]-k]
k-=dfn[root]-dfn[u]+1
root=fa[u]
def route_query(self,u,v): #查询u到v简单路径
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
route=[]
while top[u]!=top[v]:
if dep[top[u]]<dep[top[v]]:
u,v=v,u
route.append((dfn[top[u]],dfn[u]))
u=fa[top[u]]
if dep[u]>dep[v]:
u,v=v,u
route.append((dfn[u],dfn[v]))
return route
def path(self,start,end): #得到start到end简单路径的所有节点
fa=self.fa;size=self.size;dep=self.dep;son=self.son
dfn=self.dfn;top=self.top;rank=self.rank
mid=self.lca(start,end)
ps=[]
while start!=mid:
ps.append(start)
start=fa[start]
pe=[]
while end!=mid:
pe.append(end)
end=fa[end]
return ps+[mid]+pe[::-1]
n=ii()
s=[0]+li()
c=[0]+li()
g=[[] for _ in range(n+1)]
for _ in range(n-1):
u,v=li()
g[u]+=[v]
g[v]+=[u]
hld=HLD(g,1)
nums=[(0,0,0,0) for _ in range(n+1)]
for i in range(1,n+1):
nums[hld.dfn[i]]=(s[i]%mod,c[i],0,1)
def op2(x,y):
return ((x[0]+y[0])%mod,(x[1]+y[1])%mod,(x[2]+y[2])%mod,x[3]+y[3])
def mapping(f,s):
return ((s[0]+f[0]*s[2]+f[1]*s[1]+f[0]*f[1]*s[3])%mod,(s[1]+f[0]*s[3])%mod,(s[2]+f[1]*s[3])%mod,s[3])
def composition(x,y):
return ((x[0]+y[0])%mod,(x[1]+y[1])%mod)
seg=LazySegTree(nums,op2,(0,0,0,0),mapping,composition,(0,0))
q=ii()
# for _ in range(q):
# s=li()
# if s[0]==1:
# l,r,x=s[1:]
# seg.apply(l-1,r-1,(x%mod,0))
# elif s[0]==2:
# l,r,x=s[1:]
# seg.apply(l-1,r-1,(0,x%mod))
# else:
# l,r=s[1:]
# print(seg.prod(l-1,r-1)[0]%mod)
for _ in range(q):
op=li()
if op[0]==0:
x,y,z=op[1:]
for u,v in hld.route_query(x,y):
seg.apply(u,v,(0,z%mod))
else:
x,y=op[1:]
res=0
for u,v in hld.route_query(x,y):
res=(res+seg.prod(u,v)[0])%mod
print(res)