初めてqiitaで記事を書きます。読みにくい点などもあるかと思いますが優しい目でお願いします。質問等は随時受け付けています。
自己紹介
大阪大学2回生で競技プログラミング部rainbou副部長、Atcoder緑
X:https://x.com/e4h99rhQ7I24670
問題文（村人の友好関係 (paizaランク S 相当)）
解説
まず、この問題はpaizaのなかでもかなり難しい問題だと思います。体感はAtcoderで1200diff程度だと思っています。
以下具体的な解法に触れていこうと思います。
制約等から愚直解ではrun time errorすることは自明です。
なぜなら計算量がO(QN^2)である。
そのため、なにか高速化できるかどうかを検討します。
ここで、頂点Ａと頂点Ｂの属性が違った時、その頂点間のパス（最短でなくてもよい）のうち最小の重みが最大であるパスのみを考えればいいことが分かります。
これは最初に辺の情報を入力として受け取った後に辺の重みでソートして、最大辺から考慮し頂点をUnionしていき、両端とも同じ属性に属している場合はその辺が使われる（答えになる）ことはないので無視します。
A.sort(key=lambda x: (x[1]), reverse=True)
Aを二重リストで受け取った後にこの行を書くと、要素の２番目の降順にソートしてくれます。
ACコード
class UnionFind:
# インデックスは0-start
# 初期化
def __init__(self, n):
self.n = n
self.parents = [-1] * n
self.group = n
# private function
def find(self, x):
if self.parents[x] < 0:
return x
else:
vertices = []
while self.parents[x] >= 0:
vertices.append(x)
x = self.parents[x]
for i in vertices:
self.parents[i] = x
return x
# x,yが属するグループの結合
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
'''
以下消すかどうかその都度考える
'''
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
self.group -= 1
# x,yが同グループか判定
def same(self, x, y):
return self.find(x) == self.find(y)
# xと同じグループの要素数を取得
def size(self, x):
return -self.parents[self.find(x)]
# xが親かを判定
def isparent(self, x):
return self.parents[x] < 0
'''
同じ群にいるかどうかの判定はsame(x, y)でおこなう
26, 27行目のunion-by-sizeは行ってはいけないときがある。
そのグループの中で親が変わってはいけないとき
'''
N, M, Q = map(int, input().split())
doukoukai = [False]*N
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda x: (x[2]), reverse=True)
UF = UnionFind(N)
edge = []
for i in range(M):
a, b, f = AB[i]
a -= 1
b -= 1
if UF.same(a, b):
continue
UF.union(a, b)
edge.append((a, b, f))
for i in range(Q):
op, q = map(str, input().split())
q = int(q)-1
ans = 0
if op == '+':
doukoukai[q] = True
else:
doukoukai[q] = False
for a, b, f in edge:
if doukoukai[a] != doukoukai[b]:
ans = max(ans, f)
print(ans)
なにか質問等ございましたら、X等で言ってください。