#1002013 (PyPy3) No.399 動的な領主

• 問題: No.399 動的な領主
• ユーザー: N-noa21
• 提出日時: 2024-08-15 14:00:00
• 言語: PyPy3 (7.3.15)
• 結果: WA
• 実行時間: -
• コード長: 3,826 bytes
• コンパイル時間: 245 ms
• コンパイル使用メモリ: 82,380 KB
• 実行使用メモリ: 98,304 KB
• 最終ジャッジ日時: 2024-08-15 14:00:12
• 合計ジャッジ時間: 9,565 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 5 WA * 14

ソースコード

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
class HeavyLightDecomposition:#N,edge
    def __init__(self,n,edge):
        self.n=n
        self.size=[1]*n
        self.par=[-1]*n
        que=[0]
        while que:#親とこの数を数える段階
            v=que.pop()
            if v>=0:#向かう点が0以上なら木を下る、0未満なら木を登る、下る際には今見ている辺の上向き、下向きを準備して親を定義する
                for u in edge[v]:
                    if u!=self.par[v]:
                        que.append(~u)
                        que.append(u)
                        self.par[u]=v
            else:#上向きではこの数を伝搬する
                v=~v
                self.size[self.par[v]]+=self.size[v]
        self.head=[-1]*n#heavy辺上なら連結しているなかで一番上に位置する点
        self.head[0]=0
        self.order=[-1]*n#振り直された番号
        self.heavy_child=[-1]*n#自分とheavy辺を張られた子
        que=[0]
        cnt=0
        while que:
            v=que.pop()
            self.order[v]=cnt
            cnt+=1
            mx=0
            for u in edge[v]:#heavy辺を決める
                if u!=self.par[v] and mx<self.size[u]:
                    mx=self.size[u]
                    self.heavy_child[v]=u
            for u in edge[v]:#light辺なのでheadは自分自身   
                if self.par[v]!=u and self.heavy_child[v]!=u:
                    self.head[u]=u
                    que.append(u)
            if self.heavy_child[v]!=-1:
                self.head[self.heavy_child[v]]=self.head[v]
                que.append(self.heavy_child[v])
    
    def decomposition(self,u,v):#HL分解により処理された辺を返す
        paths=[]
        while True:
            if self.order[u]>self.order[v]:
                u,v=v,u
            if self.head[u]!=self.head[v]:#自分を含むheavy辺が同じ
                paths.append((self.order[self.head[v]],self.order[v]+1))
                v=self.par[self.head[v]]
            else:
                paths.append((self.order[u]+1,self.order[v]+1))
                paths.append((self.par[u]+1,self.par[u]+2))
                return paths
    
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int, input().split())
    u-=1;v-=1
    edge[u].append(v)
    edge[v].append(u)
HLD = HeavyLightDecomposition(N,edge)
#print(HLD.order)
"""
#セグ木に乗せる例(距離)
#セグ木の初期化
if HLD.par[a] == b:#aが子なら整理した順序のorder上のaにaとbの辺の重さwを持たせる
    l[HLD.order[a]] = w
else:#それの逆
    l[HLD.order[b]] = w
seg = Segtree(l,0,f)
#aが親で、a-b間の辺の重さをxに変更
if HLD.par[a] == b:#aが子なら整理した順序のorder上のaにaとbの辺の重さxを持たせる
    l[HLD.order[a]] = x
else:#それの逆
    l[HLD.order[b]] = x
#u~vの間の距離の和
for e_u,e_v in HLD.decomposition(u,v):#分解した区間ごとに足す
    ans += seg.query(e_u,e_v)
"""
data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)
# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)
Q = int(input())
ans = 0
for i in range(Q):
    a,b = map(int, input().split())
    a-=1;b-=1
    for j,k in HLD.decomposition(a,b):
        add(j+1,k+1,1)
    #print(HLD.decomposition(a,b))
for i in range(1,N+1):
    tmp = query(i,i+1)
    ans += (1+tmp) * tmp //2
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX