Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // D(2).cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
- //
- #include <iostream>
- #include<vector>
- #include<algorithm>
- #include<math.h>
- #include<set>
- #include<map>
- #include<unordered_map>
- #include<string>
- #include<unordered_set>
- #pragma GCC optimize("Ofast")
- #pragma GCC optimize("unroll-loops")
- #include <cassert>
- using namespace std;
- #define int long long
- typedef long long lli;
- typedef long double ld;
- ld PI = 3.1415926535897932384626433832;
- const double E = 0.0000001;
- const int INF = 1e7;
- #define forn(i, s, f) for (int i = s; i < f; ++i)
- #define ft first
- #define sec second
- #define fora(i, n) for (auto i : n)
- #define sz(a) (int)(a).size()
- #define sort_(a) sort(a.begin(), a.end())
- #define pb push_back
- #define mp make_pair
- #define fast_ cin.tie(0), ios_base::sync_with_stdio(false);
- vector<int> tout, tin, pr;
- vector<vector<int>> ver;
- int con = 30, timer = 0;
- map<pair<int, int>, int> M;
- void upd(int v, int l, int r, int in, int val, vector<int>& t) {
- if (l == r) {
- t[v] += val;
- }
- else {
- int m = (l + r) / 2;
- if (m >= in) {
- upd(v * 2, l, m, in, val, t);
- }
- else {
- upd(v * 2 + 1, m + 1, r, in, val, t);
- }
- t[v] = t[v * 2] + t[v * 2 + 1];
- }
- }
- int get(int v, int l, int r, int l2, int r2, vector<int>& t) {
- if (l == l2 && r == r2) {
- return t[v];
- }
- else {
- int m = (l + r) / 2;
- if (m >= r2) {
- return get(v * 2, l, m, l2, r2, t);
- }
- else if (m < l2) {
- return get(v * 2 + 1, m + 1, r, l2, r2, t);
- }
- else {
- return get(v * 2, l, m, l2, m, t) + get(v * 2 + 1, m + 1, r, m + 1, r2, t);
- }
- }
- }
- void dfs(int v, int p, vector<vector<int>>& g) {
- tin[v] = timer;
- timer++;
- pr[v] = p;
- fora(u, g[v]) {
- if (u != p) {
- dfs(u, v, g);
- }
- }
- tout[v] = timer;
- timer++;
- }
- bool pre(int v, int u) {
- return tin[v] <= tin[u] && tout[u] <= tout[v];
- }
- int lca(int v, int u, vector<vector<int>>& lc) {
- if (pre(v, u)) {
- return v;
- }
- if (pre(u, v)) {
- return u;
- }
- for (int i = con - 1; i >= 0; i--) {
- // cout << i << " "<< v << "\n";
- if (!pre(lc[i][v], u)) {
- v = lc[i][v];
- }
- }
- return lc[0][v];
- }
- void dfs(int v, int pr, int le, vector<vector<pair<int, int>>>& g, vector<int> &t) {
- if (le != -1) {
- upd(1, 0, 1e6, le, 1, t);
- }
- fora(j, ver[v]) {
- M[{v, j}] = get(1, 0, 1e6, 0, j, t);
- //cout << "M " << v << " " << j << " " << M[{v, j}] << endl;
- }
- fora(u, g[v]) {
- if (u.ft != pr) {
- dfs(u.ft, v, u.second, g, t);
- }
- }
- if (le != -1) {
- upd(1, 0, 1e6, le, -1, t);
- }
- }
- signed main()
- {
- fast_;
- int n, q;
- cin >> n >> q;
- vector<vector<pair<int, int>>> g(n);
- vector<vector<int>> gr(n);
- forn(i, 0, n - 1) {
- int a, b, le;
- cin >> a >> b >> le;
- a--;
- b--;
- g[a].pb({ b, le });
- g[b].pb({ a, le });
- gr[a].pb(b);
- gr[b].pb(a);
- }
- vector<vector<int>> lc(con, vector<int>(n));
- pr.resize(n);
- tin.resize(n);
- tout.resize(n);
- dfs(0, -1, gr);
- //cout << "A\n";
- pr[0] = 0;
- forn(i, 0, n) {
- lc[0][i] = pr[i];
- }
- forn(i, 1, n) {
- forn(j, 0, n) {
- lc[i][j] = lc[i - 1][lc[i - 1][j]];
- }
- }
- ver.resize(n);
- vector<pair<int, pair<int, int>>> qu(q);
- forn(i, 0, q) {
- int a, b, x;
- cin >> a >> b >> x;
- a--;
- b--;
- ver[a].pb(x);
- ver[b].pb(x);
- int w = lca(a, b, lc);
- // cout << w << endl;
- ver[w].pb(x);
- qu[i] = { x, {a, b} };
- }
- vector<int> t((1e6 + 1) * 4, 0);
- dfs(0, -1, -1, g, t);
- //vector<int> ans(q);
- forn(i, 0, q) {
- int an = 0;
- int w = lca(qu[i].second.ft, qu[i].second.second, lc);
- an += M[{qu[i].second.ft, qu[i].ft}];
- an += M[{qu[i].second.second, qu[i].ft}];
- an -= 2 * M[{w, qu[i].ft}];
- // ans[i] = an;
- cout << an << "\n";
- }
- return 0;
- }
- // Запуск программы: CTRL+F5 или меню "Отладка" > "Запуск без отладки"
- // Отладка программы: F5 или меню "Отладка" > "Запустить отладку"
- // Советы по началу работы
- // 1. В окне обозревателя решений можно добавлять файлы и управлять ими.
- // 2. В окне Team Explorer можно подключиться к системе управления версиями.
- // 3. В окне "Выходные данные" можно просматривать выходные данные сборки и другие сообщения.
- // 4. В окне "Список ошибок" можно просматривать ошибки.
- // 5. Последовательно выберите пункты меню "Проект" > "Добавить новый элемент", чтобы создать файлы кода, или "Проект" > "Добавить существующий элемент", чтобы добавить в проект существующие файлы кода.
- // 6. Чтобы снова открыть этот проект позже, выберите пункты меню "Файл" > "Открыть" > "Проект" и выберите SLN-файл.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement