[Vani有约会]雨天的尾巴

嘟嘟嘟




看到链上操作，自然想到树剖。

先考虑序列上的问题：那么区间修改可以用差分。所以我们把操作拆成\(L\)和\(R + 1\)两个点，然后离线。排序后扫一遍，用线段树维护数量最多的颜色是哪一个。




现在改成了树上，那么就用树剖把链变成一段段区间，然后做法和上面就一样了。

复杂度\(O(n ^ 2logn)\)。




（据说这题还有线段树合并的做法，但是我没想出来）

#include<cstdio>

#include<iostream>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<vector>

#include<stack>

#include<queue>

using namespace std;

#define enter puts("")

#define space putchar(' ')

#define Mem(a, x) memset(a, x, sizeof(a))

#define In inline

typedef long long ll;

typedef double db;

const int INF = 0x3f3f3f3f;

const db eps = 1e-8;

const int maxn = 1e5 + 5;

const int maxq = 4e6 + 5;

inline ll read()

{

  ll ans = 0;

  char ch = getchar(), last = ' ';

  while(!isdigit(ch)) last = ch, ch = getchar();

  while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();

  if(last == '-') ans = -ans;

  return ans;

}

inline void write(ll x)

{

  if(x < 0) x = -x, putchar('-');

  if(x >= 10) write(x / 10);

  putchar(x % 10 + '0');

}

int n, m;

struct Edge

{

  int nxt, to;

}e[maxn << 1];

int head[maxn], ecnt = -1;

In void addEdge(int x, int y)

{

  e[++ecnt] = (Edge){head[x], y};

  head[x] = ecnt;

}

int dep[maxn], siz[maxn], son[maxn], fa[maxn];

In void dfs1(int now, int _f)

{

  siz[now] = 1;

  for(int i = head[now], v; ~i; i = e[i].nxt)

    {

      if((v = e[i].to) == _f) continue;

      dep[v] = dep[now] + 1;

      fa[v] = now;

      dfs1(v, now);

      siz[now] += siz[v];

      if(!son[now] || siz[son[now]] < siz[v]) son[now] = v;

    }

}

int dfsx[maxn], pos[maxn], top[maxn], cnt = 0;

In void dfs2(int now, int _f)

{

  dfsx[now] = ++cnt; pos[cnt] = now;

  if(son[now]) top[son[now]] = top[now], dfs2(son[now], now);

  for(int i = head[now], v; ~i; i = e[i].nxt)

    {

      if((v = e[i].to) == _f || v == son[now]) continue;

      top[v] = v, dfs2(v, now);

    }

}

struct Node

{

  int id, flg, col;

  In bool operator < (const Node& oth)const

  {

    return id < oth.id;

  }

}q[maxq];

int qcnt = 0;

In void solve(int x, int y, int col)

{

  while(top[x] ^ top[y])

    {

      if(dep[top[x]] < dep[top[y]]) swap(x, y);

      q[++qcnt] = (Node){dfsx[top[x]], 1, col};

      q[++qcnt] = (Node){dfsx[x] + 1, -1, col};

      x = fa[top[x]];

    }

  if(dfsx[x] < dfsx[y]) swap(x, y);

  q[++qcnt] = (Node){dfsx[y], 1, col};

  q[++qcnt] = (Node){dfsx[x] + 1, -1, col};

}

int Max_col;

int l[maxn << 2], r[maxn << 2], Max[maxn << 2], Mpos[maxn << 2];

In void build(int L, int R, int now)

{

  l[now] = L; r[now] = R;

  if(L == R) {Mpos[now] = L; return;}

  int mid = (L + R) >> 1;

  build(L, mid, now << 1);

  build(mid + 1, R, now << 1 | 1);

  Mpos[now] = Mpos[now << 1];

}

In void update(int id, int now, int d)

{

  if(l[now] == r[now]) {Max[now] += d; return;}

  int mid = (l[now] + r[now]) >> 1;

  if(id <= mid) update(id, now << 1, d);

  else update(id, now << 1 | 1, d);

  if(Max[now << 1] >= Max[now << 1 | 1]) Max[now] = Max[now << 1], Mpos[now] = Mpos[now << 1];

  else Max[now] = Max[now << 1 | 1], Mpos[now] = Mpos[now << 1 | 1];

}

int ans[maxn];

int main()

{

  Mem(head, -1);

  n = read(), m = read();

  for(int i = 1; i < n; ++i)

    {

      int x = read(), y = read();

      addEdge(x, y), addEdge(y, x);

    }

  dfs1(1, 0); top[1] = 1, dfs2(1, 0);

  for(int i = 1; i <= m; ++i)

    {

      int x = read(), y = read(), col = read();

      Max_col = max(Max_col, col);

      solve(x, y, col);

    }

  sort(q + 1, q + qcnt + 1);

  build(0, Max_col, 1);

  for(int i = 1, j = 1; i <= cnt; ++i)

    {

      while(q[j].id == i) update(q[j].col, 1, q[j].flg), ++j;

      ans[pos[i]] = Mpos[1];

    }

  for(int i = 1; i <= n; ++i) write(ans[i]), enter;

  return 0;

}