洛谷 P3401

甚么神仙题啊……

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <utility>

#define int long long

using namespace std;

const int N = 3e4 + 10;
int n;
int q;
int dep[N];
int sz[N];
int fa[N];
int len[N];
int rk[N];
int top[N];
int dfs_order[N];
int son[N];
int cnt;
int w[N];
int qwq[N];
int a[N];
vector <pair <int, int> > zz[N];

struct Node
{
  int l;
  int r;
  int lazy;
  int sum[15];
  int x0;
  int x1;
  int cnt0[15];
  int cnt1[15];
  Node ()
  {
    l = 0;
    r = 0;
    memset (sum, 0, sizeof sum);
    memset (cnt0, 0, sizeof cnt0);
    memset (cnt1, 0, sizeof cnt1);
    lazy = 0;
    x0 = 0;
    x1 = 0;
  }
  ~Node ()
  {
    l = 0;
    r = 0;
    memset (sum, 0, sizeof sum);
    memset (cnt0, 0, sizeof cnt0);
    memset (cnt1, 0, sizeof cnt1);
    lazy = 0;
    x0 = 0;
    x1 = 0;
  }
  void color(int p)
  {
    lazy ^= (1 << p);
    if (sum[p] == 1)
    {
      sum[p] = 0;
    }
    else
    {
      sum[p] = 1;
    }
    x0 = x0 - cnt0[p] + cnt1[p];
    x1 = x1 - cnt1[p] + cnt0[p];
    swap (cnt0[p], cnt1[p]);
  }
  void init(int p)
  {
    l = p;
    r = p;
    for (int i = 0; i < 10; i ++)
    {
      if (qwq[p] & (1 << i))
      {
        sum[i] = 1;
        cnt1[i] = 1;
      }
      else
      {
        cnt0[i] = 1;
      }
    }
    for (int i = 0; i < 10; i ++)
    {
      if (sum[i])
      {
        x1 ++;
      }
      else
      {
        x0 ++;
      }
    }
    lazy = 0;
  }
  int query()
  {
    int x = 0;
    for (int i = 9; ~i; i --)
    {
      x = x << 1 | sum[i];
    }
    return x;
  }
}
z[N << 2];

Node operator + (const Node &lhs, const Node &rhs)
{
  Node ans;
  ans.l = lhs.l;
  ans.r = rhs.r;
  for (int i = 0; i < 10; i ++)
  {
    ans.sum[i] = lhs.sum[i] + rhs.sum[i];
  }
  for (int i = 0; i < 10; i ++)
  {
    ans.cnt0[i] = lhs.cnt0[i] + rhs.cnt0[i];
  }
  for (int i = 0; i < 10; i ++)
  {
    ans.cnt1[i] = lhs.cnt1[i] + rhs.cnt1[i];
  }
  ans.lazy = 0;
  ans.x0 = lhs.x0 + rhs.x0;
  ans.x1 = lhs.x1 + rhs.x1;
  return ans;
}

void build(int l, int r, int rt)
{
  if (l == r)
  {
    z[rt].init(l);
    return ;
  }
  int mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  z[rt] = z[rt << 1] + z[rt << 1 | 1];
}

void dfs1(int now, int fat = -1)
{
  dep[now] = dep[fa[now]] + 1;
  sz[now] = 1;
  for (auto &[u, v] : zz[now])
  {
    if (u != fat)
    {
      a[u] = v;
      w[u] = w[now] ^ v;
      fa[u] = now;
      dfs1(u, now);
      sz[now] += sz[u];
      if (sz[u] > sz[son[now]])
      {
        son[now] = u;
      }
    }
  }
}

void dfs2(int now, int h, int fat = -1)
{
  cnt ++;
  dfs_order[cnt] = now;
  rk[now] = cnt;
  qwq[cnt] = w[now];
  top[now] = h;
  len[h] ++;
  int p = -1;
  for (auto &[u, v] : zz[now])
  {
    if (u != fat)
    {
      if (p == -1)
      {
        p = u;
      }
      else
      {
        if (sz[u] > sz[p])
        {
          p = u;
        }
      }
    }
  }
  if (p == -1)
  {
    return ;
  }
  dfs2(p, h, now);
  for (auto &[u, v] : zz[now])
  {
    if (p != u)
    {
      if (u != fat)
      {
        dfs2(u, u, now);
      }
    }
  }
}

int lca(int x, int y)
{
  while (top[x] != top[y])
  {
    if (dep[top[x]] < dep[top[y]])
    {
      swap(x, y);
    }
    x = fa[top[x]];
  }
  if (dep[x] < dep[y])
  {
    return x;
  }
  else
  {
    return y;
  }
}

void push_lazy(int rt)
{
  int la = z[rt].lazy;
  for (int i = 0; i < 10; i ++)
  {
    if (la & (1 << i))
    {
      z[rt << 1].color(i);
      z[rt << 1 | 1].color(i);
    }
  }
  z[rt].lazy = 0;
}

void modify(int l, int r, int rt, int nowl, int nowr, int value)
{
  if (nowl <= l)
  {
    if (r <= nowr)
    {
      z[rt].color(value);
      return ;
    }
  }
  int mid = l + r >> 1;
  push_lazy(rt);
  if (nowl <= mid)
  {
    modify(l, mid, rt << 1, nowl, nowr, value);
  }
  if (mid < nowr)
  {
    modify(mid + 1, r, rt << 1 | 1, nowl, nowr, value);
  }
  z[rt] = z[rt << 1] + z[rt << 1 | 1];
}

void modify_tree(int p, int c)
{
  for (int i = 0; i < 10; i ++)
  {
    if ((a[p] ^ c) >> i & 1)
    {
      modify(1, n, 1, rk[p], rk[p] + sz[p] - 1, i);
    }
  }
  a[p] = c;
}

int query(int l, int r, int rt, int nowl, int nowr)
{
  if (nowl <= l)
  {
    if (r <= nowr)
    {
      return z[rt].query();
    }
  }
  push_lazy(rt);
  int ans = 0;
  int mid = l + r >> 1;
  if (nowl <= mid)
  {
    ans ^= query(l, mid, rt << 1, nowl, nowr);
  }
  if (mid < nowr)
  {
    ans ^= query(mid + 1, r, rt << 1 | 1, nowl, nowr);
  }
  return ans;
}

int query_link(int p1, int p2)
{
  int ans = 0;
  while (true)
  {
    if (top[p1] == top[p2])
    {
      if (dep[p1] > dep[p2])
      {
        swap(p1, p2);
      }
      ans ^= query(1, n, 1, rk[p1], rk[p2]);
      break;
    }
    else
    {
      if (dep[top[p1]] < dep[top[p2]])
      {
        swap (p1, p2);
      }
      int p3 = top[p1];
      ans ^= query(1, n, 1, rk[p3], rk[p1]);
      p1 = fa[p3];
    }
  }
  return ans;
}

Node que(int l, int r, int rt, int nowl, int nowr)
{
  if (nowl <= l)
  {
    if (r <= nowr)
    {
      return z[rt];
    }
  }
  int mid = l + r >> 1;
  push_lazy(rt);
  if (nowr <= mid)
  {
    return que(l, mid, rt << 1, nowl, nowr);
  }
  if (mid < nowl)
  {
    return que(mid + 1, r, rt << 1 | 1, nowl, nowr);
  }
  return que(l, mid, rt << 1, nowl, nowr) + que(mid + 1, r, rt << 1 | 1, nowl, nowr);
}

int query(int x, int y)
{
  int c1[20] = {0};
  int c0[20] = {0};
  while (top[x] != top[y])
  {
    if (dep[top[x]] < dep[top[y]])
    {
      swap (x, y);
    }
    Node orz = que(1, n, 1, rk[top[x]], rk[x]);
    for (int i = 0; i < 10; i ++)
    {
      c1[i] += orz.cnt1[i];
      c0[i] += orz.cnt0[i];
    }
    x = fa[top[x]];
  }
  if (rk[x] > rk[y])
  {
    swap (x, y);
  }
  Node orz = que(1, n, 1, rk[x], rk[y]);
  for (int i = 0; i < 10; i ++)
  {
    c1[i] += orz.cnt1[i];
    c0[i] += orz.cnt0[i];
  }
  int ans = 0;
  for (int i = 0; i < 10; i ++)
  {
    ans = ans + (1 << i) * c1[i] * c0[i];
  }
  return ans;
}

signed main()
{
  cin >> n >> q;
  for (int i = 1; i < n; i ++)
  {
    int u, v, w;
    cin >> u >> v >> w;
    zz[u].push_back(make_pair(v, w));
    zz[v].push_back(make_pair(u, w));
  }
  dfs1(1);
  dfs2(1, 1);
  build(1, n, 1);
  while (q --)
  {
    int opt;
    cin >> opt;
    if (opt == 1)
    {
      int u, v;
      cin >> u >> v;
      cout << query(u, v) << '\n';
    }
    else
    {
      int u, v, w;
      cin >> u >> v >> w;
      int c = query_link(u, v);
      if (dep[u] < dep[v])
      {
        modify_tree(v, w);
      }
      else
      {
        modify_tree(u, w);
      }
    }
  }
  return 0;
}

原文地址：http://www.cnblogs.com/BaiduFirstSearch/p/16823737.html