Ask AI
Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.
Open Claude Desktoptrees · greedy · pairwise-distances
The organizer’s problem statement is available at the official source link.
tree cut
An edge contributes across its cut
Removing one tree edge splits the vertices into two groups; every cross-group pair uses that edge. Schematic structure only; vertices and edges represent the task relation, not an official sample. Schematic graph only; labels and edges show the task relation, not an official sample.
| Tree edge | Cut component sizes | Distance contribution |
|---|---|---|
| edge e, weight w | s and N-s | w * s * (N-s) |
| all edges | count crossing pairs | assign larger weights to larger factors |
- 1
Cut an edge
Let the two component sizes be s and N−s. - 2
Count paths
Exactly s × (N−s) unordered vertex pairs have a path through this edge. - 3
Match weights
Each edge weight is multiplied by its crossing-pair count, so assign larger weights to larger counts.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 charsRun output
Run your code to see output.