結果
| 問題 | No.922 東北きりきざむたん |
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2026-01-07 23:50:03 |
| 言語 | C# (.NET 10.0.101) |
| 結果 |
AC
|
| 実行時間 | 647 ms / 2,000 ms |
| コード長 | 7,238 bytes |
| 記録 | |
| コンパイル時間 | 10,227 ms |
| コンパイル使用メモリ | 168,684 KB |
| 実行使用メモリ | 283,312 KB |
| 最終ジャッジ日時 | 2026-01-07 23:50:25 |
| 合計ジャッジ時間 | 21,090 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (138 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net10.0/main.dll main -> /home/judge/data/code/bin/Release/net10.0/publish/
ソースコード
using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
static int NN => int.Parse(ReadLine());
static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
static int[] NMi => ReadLine().Split().Select(c => int.Parse(c) - 1).ToArray();
static int[][] NMap(int n) => Enumerable.Repeat(0, n).Select(_ => NMi).ToArray();
public static void Main()
{
Solve();
}
static void Solve()
{
var c = NList;
var (n, m, q) = (c[0], c[1], c[2]);
var map = NMap(m);
var query = NMap(q);
var tree = new List<int>[n];
for (var i = 0; i < n; ++i) tree[i] = new List<int>();
var uf = new UnionFindTree(n);
foreach (var edge in map)
{
tree[edge[0]].Add(edge[1]);
tree[edge[1]].Add(edge[0]);
uf.Unite(edge[0], edge[1]);
}
var weight = new int[n];
foreach (var edge in query) if (!uf.IsSameTree(edge[0], edge[1]))
{
++weight[edge[0]];
++weight[edge[1]];
}
var visited = new bool[n];
var sum = new int[n];
var len = Enumerable.Repeat(-1, n).ToArray();
var ans = 0L;
for (var i = 0; i < n; ++i) if (!visited[i])
{
sum[i] = DFS(i, tree, weight, visited);
var center = -1;
DFS2(i, -1, tree, sum[i], weight, ref center);
len[center] = 0;
var sub = 0L;
DFS3(center, tree, len, weight, ref sub);
ans += sub;
}
var stid = new int[n];
var stcount = new int[n];
var stpos = new int[n];
for (var i = 0; i < n; ++i)
{
stid[i] = uf.GetRoot(i);
stpos[i] = stcount[stid[i]];
++stcount[stid[i]];
}
var subtree = new List<int>[n][];
for (var i = 0; i < n; ++i)
{
subtree[i] = new List<int>[stcount[i]];
for (var j = 0; j < stcount[i]; ++j) subtree[i][j] = new List<int>();
}
foreach (var edge in map)
{
subtree[stid[edge[0]]][stpos[edge[0]]].Add(stpos[edge[1]]);
subtree[stid[edge[0]]][stpos[edge[1]]].Add(stpos[edge[0]]);
}
var lcalist = new LCA[n];
for (var i = 0; i < n; ++i) if (stcount[i] > 0) lcalist[i] = new LCA(subtree[i]);
foreach (var edge in query) if (uf.IsSameTree(edge[0], edge[1])) ans += lcalist[stid[edge[0]]].Distance(stpos[edge[0]], stpos[edge[1]]);
WriteLine(ans);
}
static int DFS(int cur, List<int>[] tree, int[] weight, bool[] visited)
{
visited[cur] = true;
var sum = weight[cur];
foreach (var next in tree[cur])
{
if (visited[next]) continue;
sum += DFS(next, tree, weight, visited);
}
return sum;
}
static int DFS2(int cur, int prev, List<int>[] tree, int s, int[] weight, ref int center)
{
var sum = weight[cur];
foreach (var next in tree[cur])
{
if (prev == next) continue;
sum += DFS2(next, cur, tree, s, weight, ref center);
}
if (center < 0 && sum * 2 >= s) center = cur;
return sum;
}
static void DFS3(int cur, List<int>[] tree, int[] len, int[] weight, ref long ans)
{
foreach (var next in tree[cur])
{
if (len[next] >= 0) continue;
len[next] = len[cur] + 1;
ans += (long)len[next] * weight[next];
DFS3(next, tree, len, weight, ref ans);
}
}
class UnionFindTree
{
int[] roots;
public UnionFindTree(int size)
{
roots = new int[size];
for (var i = 0; i < size; ++i) roots[i] = -1;
}
public int GetRoot(int a)
{
if (roots[a] < 0) return a;
return roots[a] = GetRoot(roots[a]);
}
public bool IsSameTree(int a, int b)
{
return GetRoot(a) == GetRoot(b);
}
public bool Unite(int a, int b)
{
var x = GetRoot(a);
var y = GetRoot(b);
if (x == y) return false;
if (-roots[x] < -roots[y]) { var tmp = x; x = y; y = tmp; }
roots[x] += roots[y];
roots[y] = x;
return true;
}
public int GetSize(int a)
{
return -roots[GetRoot(a)];
}
}
class LCA
{
int[] depth;
List<int>[] dmap;
public LCA(List<int>[] tree)
{
depth = new int[tree.Length];
var maxDepth = DepthList(-1, 0, 0, tree, depth);
dmap = new List<int>[tree.Length];
for (var i = 0; i < dmap.Length; ++i) dmap[i] = new List<int>();
for (var i = 0; i < dmap.Length; ++i)
{
var nx = -1;
foreach (var next in tree[i])
{
if (depth[next] < depth[i]) nx = next;
}
dmap[i].Add(nx);
}
for (int d = 2, j = 0; d <= maxDepth; d *= 2, ++j) for (var i = 0; i < dmap.Length; ++i)
{
var nx = -1;
if (dmap[i][j] > -1) nx = dmap[dmap[i][j]][j];
dmap[i].Add(nx);
}
}
public int Distance(int x, int y)
{
var (d, lca) = _Distance(x, y);
return d;
}
public int GetLCA(int x, int y)
{
var (d, lca) = _Distance(x, y);
return lca;
}
(int d, int lca) _Distance(int x, int y)
{
var res = 0;
if (depth[x] < depth[y]) { var tmp = x; x = y; y = tmp; }
while (depth[x] > depth[y])
{
for (var b = dmap[x].Count - 1; b >= 0; --b)
{
var move = 1 << b;
if (depth[x] - depth[y] >= move)
{
x = dmap[x][b];
res += move;
}
}
}
for (var b = dmap[x].Count - 1; b >= 0; --b)
{
if (dmap[x][b] != dmap[y][b])
{
x = dmap[x][b];
y = dmap[y][b];
res += 2 << b;
}
}
var lca = x;
if (x != y)
{
res += 2;
lca = dmap[x][0];
}
return (res, lca);
}
int DepthList(int prev, int cur, int d, List<int>[] tree, int[] depth)
{
depth[cur] = d;
var max = d;
foreach (var next in tree[cur])
{
if (next == prev) continue;
max = Math.Max(max, DepthList(cur, next, d + 1, tree, depth));
}
return max;
}
}
}