<?xml version="1.0" encoding="utf-8" standalone="yes"?>
<oembed>
  <author_name>drken1215</author_name>
  <author_url>https://blog.hatena.ne.jp/drken1215/</author_url>
  <blog_title>けんちょんの競プロ精進記録</blog_title>
  <blog_url>https://drken1215.hatenablog.com/</blog_url>
  <categories>
    <anon>AtCoder</anon>
    <anon>AtCoder500点</anon>
    <anon>ABC-E</anon>
    <anon>水色diff</anon>
    <anon>Kruskal法</anon>
    <anon>クエリ先読み</anon>
    <anon>クエリ処理問題</anon>
    <anon>グラフ</anon>
    <anon>クエリ(グラフ上)</anon>
    <anon>Union-Find</anon>
    <anon>最小全域木</anon>
    <anon>LCA</anon>
    <anon>各kに対して</anon>
    <anon>思わず解きたくなる興味深い良問</anon>
    <anon>そのまま覚えたい典型問題</anon>
    <anon>サイクル</anon>
    <anon>Yes/No判定問題</anon>
    <anon>全部混ぜて解く</anon>
    <anon>NoviSteps1D</anon>
  </categories>
  <description>MST の理解が問われる面白い教育的問題！ 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。 の最小全域木を とする (一意に定まることが示せる)。 このグラフに 個のクエリが与えられる。各クエリでは、2 頂点 と重み が与えられる。この重み は、元のグラフ のどの辺の重みとも異なることが保証される。 このグラフ に頂点 を結ぶ重み の辺 を追加してできるグラフ の最小全域木を とする (一意に定まることが示せる)。 が辺 を含むかどうかを判定せよ。 制約 考えたこと こういう問題大好き！ クエリ…</description>
  <height>190</height>
  <html>&lt;iframe src=&quot;https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2023%2F06%2F11%2F023548&quot; title=&quot;AtCoder ABC 235 E - MST + 1 (1D, 水色, 500 点) - けんちょんの競プロ精進記録&quot; class=&quot;embed-card embed-blogcard&quot; scrolling=&quot;no&quot; frameborder=&quot;0&quot; style=&quot;display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;&quot;&gt;&lt;/iframe&gt;</html>
  <image_url>https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660</image_url>
  <provider_name>Hatena Blog</provider_name>
  <provider_url>https://hatena.blog</provider_url>
  <published>2023-06-11 02:35:48</published>
  <title>AtCoder ABC 235 E - MST + 1 (1D, 水色, 500 点)</title>
  <type>rich</type>
  <url>https://drken1215.hatenablog.com/entry/2023/06/11/023548</url>
  <version>1.0</version>
  <width>100%</width>
</oembed>
