#991023 (PyPy3) No.1333 Squared Sum

• 問題: No.1333 Squared Sum
• ユーザー: 已经死了
• 提出日時: 2024-06-27 18:13:21
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,831 ms / 2,000 ms
• コード長: 5,521 bytes
• コンパイル時間: 1,315 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 290,372 KB
• 最終ジャッジ日時: 2024-06-27 18:14:03
• 合計ジャッジ時間: 39,140 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
other	AC * 44

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
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)]  # →↘↓↙←↖↑↗
def bootstrap(f, stack=[]):   #yield
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
n=ii()
g=[[] for _ in range(n+1)]
for _ in range(n-1):
    u,v,w=li()
    w%=mod
    g[u].append((v,w))
    g[v].append((u,w))
f1=[0]*(n+1) #i子树内所有点到i点的 距离 平方和
f2=[0]*(n+1) #i子树内所有点到i点的 距离 和
f3=[1]*(n+1) #i子树内所有点的 个数 之和
#u是父节点，v是子节点，v的的信息合并到u中
#f1[u]+=f1[v]+2*f2[v]+f3[v]
#f2[u]+=f2[v]+f3[v]
#f3[u]+=f3[v]
@bootstrap
def dfs(u,fa):
    for v,w in g[u]:
        if v==fa:
            continue
        yield dfs(v,u)
        f1[u]+=f1[v]+(2*f2[v]*w)%mod+(f3[v]*w*w)%mod
        f1[u]%=mod
        f2[u]+=f2[v]+(f3[v]*w)%mod
        f2[u]%=mod
        f3[u]+=f3[v]
        f3[u]%=mod
    yield None
dfs(1,-1)
res=[0]*(n+1)
@bootstrap
def dfs2(u,fa):
    t1=t2=t3=0
    t3+=1
    for v,w in g[u]:
        t1=(t1+f1[v]+(2*f2[v]*w)%mod+(f3[v]*w*w)%mod)%mod
        t2=(t2+f2[v]+(f3[v]*w)%mod)%mod
        t3=(t3+f3[v])%mod
    res[u]=t1
    for v,w in g[u]:
        if v==fa:
            continue
        f1[u]=(t1-(f1[v]+(2*f2[v]*w)%mod+(f3[v]*w*w)%mod))%mod
        f2[u]=(t2-(f2[v]+(f3[v]*w)%mod))%mod
        f3[u]=(t3-f3[v])%mod
        yield dfs2(v,u)
    yield None
dfs2(1,-1)
tot=sum(res)%mod
print(tot*pow(2,mod-2,mod)%mod)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX