CSU 1811 Tree Intersection

Description

i, and the i-th edge connects vertices a

i and b

Let C(x,y) denotes the set of colors in subtree rooted at vertex x deleting edge (x,y).

i,b

i) and C(b

i,a

i) for all 1≤i≤(n-1). (i.e. |C(a

i,b

i)∩C(b

i,a

i)|)

Input

The input contains at most 15 sets. For each set:

5).

1,c

2,…,c

i,b

i (1≤a

i,b

i≤n).

Output

1,R

2,…,R

n-1.

Sample Input

Sample Output

#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 in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, col[N], x, y;
int ft[N], nt[N], u[N], v[N], sz;
int Ft[N], Nt[N], U[N], V[N], Sz;
int d[N], t, pre[N], L[N], R[N];
int f[N], ans[N];

void dfs(int x, int fa)
{
  d[pre[x] = ++t] = x;
  L[col[x]] = min(L[col[x]], t);
  R[col[x]] = max(R[col[x]], t);
  loop(i, ft[x], nt)
  {
    if (u[i] == fa) continue;
    dfs(u[i], x);
    U[Sz] = pre[u[i]];  V[Sz] = v[i];
    Nt[Sz] = Ft[t];     Ft[t] = Sz++;
  }
}

void add(int x, int y)
{
  for (int i = x; i <= n; i += low(i)) f[i] += y;
}

int get(int x)
{
  int res = 0;
  for (int i = x; i; i -= low(i)) res += f[i];
  return res;
}

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    Sz = sz = t = 0;
    rep(i, 1, n) in(col[i]);
    rep(i, 1, n) Ft[i] = ft[i] = -1;
    rep(i, 1, n) L[i] = n + 1, R[i] = f[i] = 0;
    rep(i, 1, n - 1)
    {
      in(x);  in(y);
      u[sz] = y; v[sz] = i; nt[sz] = ft[x];  ft[x] = sz++;
      u[sz] = x; v[sz] = i; nt[sz] = ft[y];  ft[y] = sz++;
    }
    dfs(1, 0);
    rep(i, 1, n) pre[i] = f[i] = 0;
    rep(i, 1, n)
    {
      add(pre[col[d[i]]] + 1, 1);  add(i + 1, -1); pre[col[d[i]]] = i;
      if (i == R[col[d[i]]]) add(1, -1), add(L[col[d[i]]] + 1, 1);
      loop(j, Ft[i], Nt) ans[V[j]] = get(U[j]);
    }
    rep(i, 1, n - 1) printf("%d\n", ans[i]);
  }
  return 0;
}

換一種角度思考，同樣是樹形态，如果我們可以統計出某個節點全部兒子的情況，那麼将兒子的狀态全部合并加上目前節點的顔色就可以得到答案。

然後問題是怎麼快速的合并統計答案，這個時候可以用啟發式合并，線段樹和splay都可以輕松的完成這種操作。

#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 in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 2e6 + 10;
int n, x, y, col[N], cnt[N], ans[N], t[N];
int ft[N], nt[N], u[N], v[N], sz;
int L[M], R[M], f[M], g[M], tot;

int node()
{
  L[tot] = R[tot] = f[tot] = g[tot] = 0; return tot++;
}

void make(int &x, int l, int r, int u)
{
  if (!x) x = node();
  if (l == r) f[x] = g[x] = 1 % cnt[u];
  else
  {
    int mid = l + r >> 1;
    if (u <= mid) make(L[x], l, mid, u);
    else make(R[x], mid + 1, r, u);
    f[x] = f[L[x]] + f[R[x]];
  }
}

void merge(int &x, int y, int l, int r)
{
  if (!x || !y) { x = x^y; return; }
  if (l == r) f[x] = (bool)(g[x] = (g[x] + g[y]) % cnt[l]);
  else
  {
    int mid = l + r >> 1;
    merge(L[x], L[y], l, mid);
    merge(R[x], R[y], mid + 1, r);
    f[x] = f[L[x]] + f[R[x]];
  }
}

void dfs(int x, int fa)
{
  make(t[x] = 0, 1, n, col[x]);
  loop(i, ft[x], nt)
  {
    if (u[i] == fa) continue;
    dfs(u[i], x);
    ans[v[i]] = f[t[u[i]]];
    merge(t[x], t[u[i]], 1, n);
  }
}

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    tot = sz = 0; node();
    rep(i, 1, n) cnt[i] = 0, ft[i] = -1;
    rep(i, 1, n) { in(col[i]); cnt[col[i]]++; }
    rep(i, 1, n - 1)
    {
      in(x);  in(y);
      u[sz] = y; v[sz] = i; nt[sz] = ft[x]; ft[x] = sz++;
      u[sz] = x; v[sz] = i; nt[sz] = ft[y]; ft[y] = sz++;
    }
    dfs(1, 0);
    rep(i, 1, n - 1) printf("%d\n", ans[i]);
  }
  return 0;
}

#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 in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-9;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int M = 2e6 + 10;
int n, x, y, col[N], cnt[N], ans[N], t[N];
int ft[N], nt[N], u[N], v[N], sz;

struct Splays
{
  int ch[M][2], F[M], sz;
  int A[M], B[M], C[M];
  int Node(int f, int c, int z) 
  { 
    F[sz] = f; A[sz] = c; C[sz] = (bool)(B[sz] = z % cnt[c]); 
    ch[sz][0] = ch[sz][1] = 0; return sz++;
  }
  void clear() { sz = 1; ch[0][0] = ch[0][1] = F[0] = 0; C[0] = 0; }
  void rotate(int x, int k)
  {
    int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
    if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
    F[x] = F[y];    F[y] = x;   ch[x][k] = y;
    C[x] = C[y];    C[y] = C[ch[y][0]] + C[ch[y][1]] + (bool)B[y];
  }
  void Splay(int x, int r)
  {
    while (F[x] != r)
    {
      if (F[F[x]] == r) { rotate(x, x == ch[F[x]][0]); return; }
      int y = (x == ch[F[x]][0]), z = (F[x] == ch[F[F[x]]][0]);
      y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
    }
  }
  void insert(int &x, int fa, int y, int z)
  {
    if (!x) { x = Node(fa, y, z); return; }
    if (A[x] == y)
    {
      B[x] = (B[x] + z) % cnt[y];
      C[x] = C[ch[x][0]] + C[ch[x][1]] + (bool)B[x];
    }
    else
    {
      insert(ch[x][A[x] < y], x, y, z);
      C[x] = C[ch[x][0]] + C[ch[x][1]] + (bool)B[x];
    }
  }
  void get(int &x, int y)
  {
    for (int i = x;; i = ch[i][A[i] < y])
    {
      if (A[i] == y) { Splay(i, 0); x = i; break; }
    }
  }
  void merge(int &x, int y)
  {
    if (!y) return;
    if (B[y]) { insert(x, 0, A[y], B[y]); get(x, A[y]); }
    merge(x, ch[y][0]);
    merge(x, ch[y][1]);
  }
}solve;

void dfs(int x, int fa)
{
  solve.insert(t[x] = 0, 0, col[x], 1);
  solve.get(t[x], col[x]);
  loop(i, ft[x], nt)
  {
    if (u[i] == fa) continue;
    dfs(u[i], x);
    ans[v[i]] = solve.C[t[u[i]]];
    if (solve.C[t[u[i]]] > solve.C[t[x]])
    {
      solve.merge(t[u[i]], t[x]);
      t[x] = t[u[i]];
    }
    else solve.merge(t[x], t[u[i]]);
  }
}

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    solve.clear(); sz = 0;
    rep(i, 1, n) cnt[i] = 0, ft[i] = -1;
    rep(i, 1, n) { in(col[i]); cnt[col[i]]++; }
    rep(i, 1, n - 1)
    {
      in(x);  in(y);
      u[sz] = y; v[sz] = i; nt[sz] = ft[x]; ft[x] = sz++;
      u[sz] = x; v[sz] = i; nt[sz] = ft[y]; ft[y] = sz++;
    }
    dfs(1, 0);
    rep(i, 1, n - 1) printf("%d\n", ans[i]);
  }
  return 0;
}

CSU 1811 Tree Intersection

Description

Input

Output

Sample Input

Sample Output

繼續閱讀

UVA 590 Always on the run

FZU 1978 Repair the brackets

UVA 10344- 23 out of 5

ZOJ 3935 2016

POJ 2115 C Looooops

HDU 5381 The sum of gcd

ZOJ 1104 Leaps Tall Buildings

ZOJ 3700 Ever Dream

HDU 2821 Pusher

ZOJ 1199 Point of Intersection

UVA 1401 Remember the Word

UVA 620 Cellular Structure

ZOJ 2748 Free Kick

CSU 1567 Reverse Rot

UVA 519 Puzzle (II)

開源按鍵元件Multi_Button的使用,含測試工程