BZOJ 1468: [POJ1741]Tree

求树上距离小于等于k的点对数

使用传说中的树分治算法!
本蒟蒻本来不会这个神算法的。。直到hhs神犇教了我。。然后发现其实这个算法也不难0 0.
(另外kd-tree也是hhs神犇教本蒟蒻的 OrzOrzOrz)

树分治有边分治和点分治 这题可以用点分治解决
所谓点分治 对于一条树路径 只有经过或不经过一个点的情况
对于不经过的情况 把一颗树按这个点拆成好几颗分治就行了
考虑经过这个点的情况
对于这题 可以对这个点延伸出的几颗子树各做一次bfs
算出每颗子树中有出现的距离值
对于一棵树的距离值数组 把它排序(hash也可以)
然后枚举两颗子树 对它们做一次单调队列算答案即可
另外对于这个点就是树路径的一个端点的情况要特殊考虑
//这里用枚举两棵子树的方法可能被菊花图卡
//可把所有距离排序 求一次ans1
//再对每棵子树分别求一个自己对自己的ans2
//ans1-Σans2即为最后的ans
//因为这题数据没有卡这个的 我就没用这个算法。。

至于这个点要选哪个点 这个至关重要
每次选取当前树的重心 这样能保证时间复杂度是nlogn级的
数的重心的定义就是如果一个点是树的重心 那么他的子树节点数的最大值最小
—————-code————–

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 40005;
struct line
{
  int next, to, v;
}li[maxn * 2];
struct range
{
  int l, r;
  range(int a = 0, int b = 0) : l(a), r(b) {}
}g[maxn];
struct point
{
  int now, fa;
  ll va;
  point(int a = 0, int c = 0, ll b = 0) : now(a), fa(c), va(b) {}
};
int be[maxn], b[maxn], bb[maxn], n, m, sum[maxn], z, mi, l;
ll a[maxn], ans;
queue<int> q;
queue<point> qq;
int getnum(int no)
{
  q.push(no);
  b[no] = no;
  int ans = 0;
  while (!q.empty())
  {
    ++ans;
    int now = q.front();
    q.pop();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (bb[to] || b[to] == no) continue;
      b[to] = no;
      q.push(to);
    }
  }
  return ans;
}
int getz(int now, int tot, int fa)
{
  int mx = 0, sum = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (to == fa || bb[to]) continue;
    int t = getz(to, tot, now);
    mx = max(mx, t);
    sum += t;
  }
  ++sum;
  mx = max(mx, tot – sum);
  if (mx < mi) mi = mx, z = now;
  return sum;
}
int bfs(int now, int l, int va)
{
  qq.push(point(now, 0, va));
  while (!qq.empty())
  {
    point now = qq.front();
    qq.pop();
    a[l++] = now.va;
    if (now.va <= m) ++ans;
    for (int i = be[now.now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (bb[to] || to == now.fa) continue;
      qq.push(point(to, now.now, now.va + li[i].v));
    }
  }
  return l – 1;
}
void getans(range u, range v)
{
  int r = v.r;
  for (int i = u.l; i <= u.r; ++i)
  {
    while (r >= v.l && a[r] + a[i] > m) –r;
    ans += r – v.l + 1;
  }
}
void dfs(int now)
{
  mi = 0x7fffffff;
  getz(now, getnum(now), 0);
  int t = z;
  bb[t] = 1;
  int la = 0, k = 0;
  for (int i = be[t]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (bb[to]) continue;
    g[k].l = la;
    la = g[k++].r = bfs(to, la, li[i].v);
    ++la;
  }
  for (int i = 0; i < k; ++i) sort(a + g[i].l, a + g[i].r + 1);
  for (int i = 0; i < k; ++i)
    for (int j = i + 1; j < k; ++j)
      getans(g[i], g[j]);
  for (int i = be[t]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (bb[to]) continue;
    dfs(to);
  }
}
void makeline(int fr, int to, int v)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
  li[l].v = v;
}
int main()
{
  scanf(“%d”, &n);
  for (int i = 1; i < n; ++i)
  {
    int fr, to, v;
    scanf(“%d%d%d”, &fr, &to, &v);
    makeline(fr, to, v);
    makeline(to, fr, v);
  }
  scanf(“%d”, &m);
  dfs(1);
  printf(“%lld”, ans);
}

发表评论