Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
using namespace std; struct DSU { vector
a; vector
b; int n; DSU (int N) { n = N; a.resize(n); b.resize(n); for(int i = 0; i < n; i ++) { a[i] = i; b[i] = 1; } } int leader(int x) { if(a[x] == x) return x; return a[x] = leader(a[x]); } void merge(int x, int y) { x = leader(x); y = leader(y); if(b[x] < b[y]) swap(x, y); b[x] += b[y]; a[y] = x; } int size(int x) { return b[leader(x)]; } }; struct lol { int x, y, c; }; bool cmp1(lol a, lol b) { return a.c > b.c; } bool cmp2(lol a, lol b) { return a.x > b.x; } bool cmp3(lol a, lol b) { return a.c < b.c; } int main() { freopen("mootube.in", "r", stdin); freopen("mootube.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; DSU dsu(n); vector
a(n); for(int i = 0; i < n - 1; i ++) { cin >> a[i].x >> a[i].y >> a[i].c; a[i].x --; a[i].y --; } vector
b(q); for(int i = 0; i < q; i ++) { cin >> b[i].x >> b[i].y; b[i].y --; b[i].c = i; } sort(a.begin(), a.end(), cmp1); sort(b.begin(), b.end(), cmp2); for(int i = 0, j = 0; i < q; i ++) { while(j < n && a[j].c >= b[i].x) { dsu.merge(a[j].x, a[j].y); j ++; } b[i].x = dsu.size(b[i].y) - 1; } sort(b.begin(), b.end(), cmp3); for(int i = 0; i < q; i ++) { cout << b[i].x << '\n'; } }
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)