LOJ2359. 「NOIP2016」天天爱跑步【树上差分】

思路

首先发现如果对于一个节点，假设一个节点需要统计从字数内来的贡献

需要满足\(dep_u - dep_s = w_u\)

这个条件其实可以转化成\(dep_u - w_u = dep_s\)

然后对于这个东西我们只需要记录下\(dep_s\)的信息就好了

然后考虑差分，把一个询问先分解成\(s->lca\)和\(lca->t\)两部分

接着把连边分别差分处理就可以了

从子树以外的地方的贡献也很好维护

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

//typename

typedef long long ll;

//convenient for

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

//inf of different typename

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

//fast read and write

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = 3e5;

struct Node{

  int u, len, typ, dir;

  //typ 1:insert -1:erase

  //dir 1:up 0:down

};

vector<Node> g[N];

struct Edge{

  int v, nxt;

} E[N << 1];

int head[N], tot = 0;

int down[N << 1], up[N << 1];

int Log[N], dep[N], w[N];

int Fa[N][18];

int n, m, ans[N];

void add(int u, int v) {

  E[++tot] = (Edge) {v, head[u]};

  head[u] = tot;

}

void dfs(int u, int fa) {

  dep[u] = dep[fa] + 1;

  Fa[u][0] = fa;

  fu(i, 1, Log[dep[u]]) Fa[u][i] = Fa[Fa[u][i - 1]][i - 1];

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (v == fa) continue;

    dfs(v, u);

  }

}

int Lca(int u, int v) {

  if (dep[u] < dep[v]) swap(u, v);

  int delta = dep[u] - dep[v];

  fu(i, 0, Log[delta])

    if ((delta >> i) & 1)

     u = Fa[u][i];

  if (u == v) return u;

  int k = Log[dep[u]];

  while (Fa[u][0] != Fa[v][0]) {

    if (Fa[u][k] != Fa[v][k]) {

      u = Fa[u][k];

      v = Fa[v][k];

    }

    k--;

  }

  return Fa[u][0];

}

void solve(int u) {

  ans[u] -= down[w[u] - dep[u] + N] + up[w[u] + dep[u]];

  fv(j, g[u]) {

    Node now = g[u][j];

    if (now.dir) up[now.len] += now.typ;

    else down[now.len] += now.typ;

  }

  for (int i = head[u]; i; i = E[i].nxt) {

    int v = E[i].v;

    if (v == Fa[u][0]) continue;

    solve(v);

  }

  ans[u] += down[w[u] - dep[u] + N] + up[w[u] + dep[u]];

}

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  Read(n), Read(m);

  Log[1] = 0; fu(i, 2, n) Log[i] = Log[i >> 1] + 1;

  fu(i, 2, n) {

    int u, v;

    Read(u), Read(v);

    add(u, v);

    add(v, u);

  }

  dfs(1,0);

  fu(i, 1, n) Read(w[i]);

  fu(i, 1, m) {

    int u, v;

    Read(u), Read(v);

    int lca = Lca(u, v);

    g[u].push_back((Node){u, dep[u], 1, 1});

    g[Fa[lca][0]].push_back((Node){Fa[lca][0], dep[u], -1, 1});

    g[v].push_back((Node){v, dep[u] - 2 * dep[lca] + N, 1, 0});

    g[lca].push_back((Node){lca, dep[u] - 2 * dep[lca] + N, -1, 0});

  }

  solve(1);

  fu(i, 1, n) {

    Write(ans[i]);

    putchar(' ');

  }

  return 0;

}

巴特西

LOJ2359. 「NOIP2016」天天爱跑步【树上差分】

思路

最新文章

热门文章