UVALive 7148 LRIP

2014年上海区域赛的K题，树上点分治，查找差值小于等于D的非严格单调序列的最长长度。

对于每个点，维护从该点出发的上升序列同长度的最小值和下降序列的同长度最大值，二分之前的得到答案。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define inone(x) scanf("%d", &x);
#define intwo(x,y) scanf("%d%d", &x, &y);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int T, n, D, x, y, ans, cas = 0;
int ft[N], nt[N], u[N], v[N], sz;
int vis[N], mx[N], ct[N];
int a[N], b[N], A[N], B[N];
int aa, bb, AA, BB;

int dfs(int x, int fa, int t)
{
  int y = mx[x] = (ct[x] = 1) ^ 1;
  loop(i, ft[x], nt)
  {
    if (vis[u[i]] || u[i] == fa) continue;
    int z = dfs(u[i], x, t);
    ct[x] += ct[u[i]];
    mx[x] = max(ct[u[i]], mx[x]);
    y = mx[y] < mx[z] ? y : z;
  }
  mx[x] = max(mx[x], t - ct[x]);
  return mx[x] < mx[y] ? x : y;
}

void find(int x, int fa, int d, int dep)
{
  if (d >= 0)
  {
    if (AA < dep) A[AA = dep] = v[x];
    else A[dep] = max(A[dep], v[x]);
  }
  if (d <= 0)
  {
    if (BB < dep) B[BB = dep] = v[x];
    else B[dep] = min(B[dep], v[x]);
  }
  loop(i, ft[x], nt)
  {
    if (vis[u[i]] || u[i] == fa) continue;
    if (1LL * d * (v[x] - v[u[i]]) < 0) continue;
    find(u[i], x, d ? d : v[x] - v[u[i]], dep + 1);
  }
}

void solve(int x)
{
  aa = bb = 1;
  a[1] = b[1] = v[x];
  loop(i, ft[x], nt)
  {
    if (vis[u[i]]) continue;
    AA = BB = 0;
    find(u[i], x, v[x] - v[u[i]], 1);
    rep(j, 1, AA)
    {
      int l = 1, r = bb, m;
      while (l <= r)
      {
        m = l + r >> 1;
        if (b[m] - A[j] > D) r = m - 1; else l = m + 1;
      }
      if (r) ans = max(ans, r + j);
    }
    rep(j, 1, BB)
    {
      int l = 1, r = aa, m;
      while (l <= r)
      {
        m = l + r >> 1;
        if (B[j] - a[m] > D) r = m - 1; else l = m + 1;
      }
      if (r) ans = max(ans, r + j);
    }
    rep(j, 1, AA)
    {
      if (aa < j + 1) a[++aa] = A[j];
      else a[j + 1] = max(A[j], a[j + 1]);
    }
    rep(j, 1, BB)
    {
      if (bb < j + 1) b[++bb] = B[j];
      else b[j + 1] = min(B[j], b[j + 1]);
    }
  }
}

void work(int r, int t)
{
  int x = dfs(r, 0, t);
  solve(x); vis[x] = 1;
  loop(i, ft[x], nt)
  {
    if (vis[u[i]]) continue;
    work(u[i], ct[u[i]] < t ? ct[u[i]] : t - ct[x]);
  }
}

int main()
{
  inone(T);
  while (T--)
  {
    intwo(n, D);
    mx[0] = INF; ans = 1; sz = 0;
    rep(i, 1, n) vis[i] = 0, ft[i] = -1, inone(v[i]);
    rep(i, 1, n - 1)
    {
      intwo(x, y);
      u[sz] = y; nt[sz] = ft[x]; ft[x] = sz++;
      u[sz] = x; nt[sz] = ft[y]; ft[y] = sz++;
    }
    work(1, n);
    printf("Case #%d: %d\n", ++cas, ans);
  }
  return 0;
}