60求助!
查看原帖
60求助!
186546
lwyznoip楼主2025/1/23 20:15
#include <cstdio>
#include <iostream>
#include <vector>
#include <utility>
#define int long long

const int N = 100005;

namespace Seg {
class Node {
public:
  std::pair<int, int> max;
  int lc, rc;
} tre[N * 60];
int tot;
int rot[N];

void pushup(int x);
void insert(int &x, int xl, int xr, int ux, int val);
int merge(int x, int y, int xl, int xr);
}

void dfs1(int u, int fa);
void dfs2(int u, int fa);
int LCA(int u, int v);

std::vector<int> G[N];
int f[N][20], dep[N];
int ans[N];
int n, m;

signed main() {
  scanf("%lld %lld", &n, &m);
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%lld %lld", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs1(1, 0);
  for (int i = 1; i <= m; i++) {
    using namespace Seg;
    int x, y, z;
    scanf("%lld %lld %lld", &x, &y, &z);
    int lca = LCA(x, y);
    insert(rot[x], 1, 100000, z, 1);
    insert(rot[y], 1, 100000, z, 1);
    insert(rot[lca], 1, 100000, z, -1);
    if (f[lca][0]) insert(rot[f[lca][0]], 1, 100000, z, -1);
  }
  dfs2(1, 0);
  for (int i = 1; i <= n; ++i) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

void Seg::pushup(int x) {
  if (tre[x].lc) tre[x].max = std::max(tre[x].max, tre[tre[x].lc].max);
  if (tre[x].rc) tre[x].max = std::max(tre[x].max, tre[tre[x].rc].max);
}
void Seg::insert(int &x, int xl, int xr, int ux, int val) {
  if (!x) x = ++tot;
  if (xl == xr) {
    tre[x].max.first += val;
    tre[x].max.second = -xl;
    return;
  }
  int xm = (xl + xr) >> 1;
  if (ux <= xm) insert(tre[x].lc, xl, xm, ux, val);
  else insert(tre[x].rc, xm + 1, xr, ux, val);
  pushup(x);
}
int Seg::merge(int x, int y, int xl, int xr) {
  if (!x || !y) return x | y;
  if (xl == xr) {
    tre[x].max.first += tre[y].max.first;
    return x;
  }
  int xm = (xl + xr) >> 1;
  tre[x].lc = merge(tre[x].lc, tre[y].lc, xl, xm);
  tre[x].rc = merge(tre[x].rc, tre[y].rc, xm + 1, xr);
  pushup(x);
  return x;
}

void dfs1(int u, int fa) {
  f[u][0] = fa;
  for (int k = 1; k < 20; ++k) {
    f[u][k] = f[f[u][k - 1]][k - 1];
  }
  for (int v : G[u]) {
    if (v == fa) continue;
    dep[v] = dep[u] + 1;
    dfs1(v, u);
  }
}
int LCA(int u, int v) {
  if (dep[u] < dep[v]) {
    std::swap(u, v);
  }
  int tmp = dep[u] - dep[v];
  for (int k = 19; k >= 0; --k) {
    if (tmp >> k & 1) {
      u = f[u][k];
    }
  }
  if (u == v) return v;
  for (int k = 19; k >= 0; --k) {
    if (f[u][k] != f[v][k]) {
      u = f[u][k], v = f[v][k];
    }
  }
  return f[u][0];
}

void dfs2(int u, int fa) {
  using namespace Seg;
  for (int v : G[u]) {
    if (v == fa) continue;
    dfs2(v, u);
    rot[u] = merge(rot[u], rot[v], 1, 100000);
  }
  if (tre[rot[u]].max.first != 0) ans[u] = -tre[rot[u]].max.second;
}
2025/1/23 20:15
加载中...