ポイント分治テンプレート、例題整理
69045 ワード
1.Acwing252. ツリー
トランスファゲート
1.題意
1つのツリーの中の距離がkに等しい点の対の個数より小さいことを求めます.
1 ≤ N ≤ 1 0 4 1≤N≤10^4 1≤N≤104
2.分析
ポイント分割アルゴリズム:
木の重心
ツリーの重心とは、この点を削除した後、最大サブツリー(の点数)が最小になる点です.重心についての結論:重心を削除した後,最大サブツリーの点数は総点数/2以下であった.
そこで,1つのツリー上の問題を重心点を削除した後,いくつかのサブツリー内部の問題とサブツリー間の問題に分解することができる.これによりlogレベルの時間的複雑さが保証される.(辺分治は無理、菊図に引っかかるn)
本題について
まず重心を探し出して、それから経路がk以下の点対は以下のように分けることができます:1.2時は同じサブツリーにあります.(次のレベルの解に再帰する).2点は異なるサブツリーにあります.(本層で解く)3.一つはこの層の重心です.(本層で解く)
この階層の情報をどのように処理するかを考えます:1.この連結ブロックのすべての点から層の重心までの距離を前処理する.2.まず、同じサブツリーの重心距離とk以下の点対個数を統計し、削除する(反発原理).3.すべてのポイントペアを巡り、答えを統計します(同じサブツリーにあるかどうかにかかわらず).4.統計的には、この層の重心の個数である.
具体的な実装
1.再帰出口はbool st[]配列を定義し、どの点が重心として削除されていないかを記録し、st[u]=falseの点に再帰されるとreturnする.
2.この連通ブロックの重心までの距離(毎回再計算される)を算出するには、距離に対する対応関係を確立する必要はなく、distはq配列に直接保存すればよい.
3.この連通ブロックの重心を求めてこの層に再帰する場合、その層の重心を再計算し、その層の点数を返す注意:ここで求めた重心は必ずしも真の重心ではなく、その点を削除した後、最大サブツリーの点数は総点数/2以下である.
4.格納されたdist配列によって、答えを統計する
具体コード
(y総コードに向かって一度)
2.Acwing. ウェイト値
トランスファゲート
に言及
長さがkに等しい経路の中で、点数の最も少ない点数を求めます.
ぶんせき
ツリーの統計的な答えの問題で、大きな問題をサブ問題に分割できます.点分治で作ることができます.
コード#コード#
小結:点分治は木の上の答えを処理するために用いられ、1.統計的な答えが必要な問題.2.サブ問題に変換できる問題.点分治は特に優れたアルゴリズムではないような気がします.各層では,関連情報を再処理し,答えが異なるサブツリーにある場合&&答えがその層の重心に押されている場合を処理する.しかし重心の性質:全体の時間複雑度はlog級であるため,再帰関数が熟練した後,符号量も大きくない.
トランスファゲート
1.題意
1つのツリーの中の距離がkに等しい点の対の個数より小さいことを求めます.
1 ≤ N ≤ 1 0 4 1≤N≤10^4 1≤N≤104
2.分析
ポイント分割アルゴリズム:
木の重心
ツリーの重心とは、この点を削除した後、最大サブツリー(の点数)が最小になる点です.重心についての結論:重心を削除した後,最大サブツリーの点数は総点数/2以下であった.
そこで,1つのツリー上の問題を重心点を削除した後,いくつかのサブツリー内部の問題とサブツリー間の問題に分解することができる.これによりlogレベルの時間的複雑さが保証される.(辺分治は無理、菊図に引っかかるn)
本題について
まず重心を探し出して、それから経路がk以下の点対は以下のように分けることができます:1.2時は同じサブツリーにあります.(次のレベルの解に再帰する).2点は異なるサブツリーにあります.(本層で解く)3.一つはこの層の重心です.(本層で解く)
この階層の情報をどのように処理するかを考えます:1.この連結ブロックのすべての点から層の重心までの距離を前処理する.2.まず、同じサブツリーの重心距離とk以下の点対個数を統計し、削除する(反発原理).3.すべてのポイントペアを巡り、答えを統計します(同じサブツリーにあるかどうかにかかわらず).4.統計的には、この層の重心の個数である.
具体的な実装
1.再帰出口はbool st[]配列を定義し、どの点が重心として削除されていないかを記録し、st[u]=falseの点に再帰されるとreturnする.
if (st[u]) return;
2.この連通ブロックの重心までの距離(毎回再計算される)を算出するには、距離に対する対応関係を確立する必要はなく、distはq配列に直接保存すればよい.
void get_dist(int u, int fa, int dist, int& qt)
{
if (st[u]) return;
q[qt ++ ] = dist;
for (int i = h[u]; ~i; i = ne[i])
if (e[i] != fa)
get_dist(e[i], u, dist + w[i], qt);
}
3.この連通ブロックの重心を求めてこの層に再帰する場合、その層の重心を再計算し、その層の点数を返す注意:ここで求めた重心は必ずしも真の重心ではなく、その点を削除した後、最大サブツリーの点数は総点数/2以下である.
int get_wc(int u, int fa, int tot, int &wc) // ,
{
if (st[u])
return 0;
int sum = 1, ms = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
int t = get_wc(j, u, tot, wc);
ms = max(ms, t); //ms size
sum += t;
}
ms = max(ms, tot - sum);
if (ms <= tot / 2)
wc = u;
return sum;
}
4.格納されたdist配列によって、答えを統計する
int get(int a[], int len) // , k
{
sort(a, a + len);
int res = 0;
for (int i = len - 1, j = -1; i >= 0; i--)
{
while (j + 1 < i && a[j + 1] + a[i] <= k)
j++;
j = min(j, i - 1);
res += j + 1;
}
return res;
}
具体コード
(y総コードに向かって一度)
#include
'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)
//---------------
// ： ，
// ： k
const int N = 1e4 + 10;
int n, k;
int h[N], e[N << 1], w[N << 1], ne[N << 1], idx;
bool st[N];
int q[N], p[N];
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int get_size(int u, int fa) //
{
if (st[u])
return 0;
int res = 1;
for (int i = h[u]; ~i; i = ne[i])
{
if (e[i] != fa)
res += get_size(e[i], u);
}
return res;
}
void get_dist(int u, int fa, int dist, int &qt) // root dist q
{
if (st[u])
return;
q[qt++] = dist;
for (int i = h[u]; ~i; i = ne[i])
if (e[i] != fa)
get_dist(e[i], u, dist + w[i], qt);
}
int get_wc(int u, int fa, int tot, int &wc) // ,
{
if (st[u])
return 0;
int sum = 1, ms = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa)
continue;
int t = get_wc(j, u, tot, wc);
ms = max(ms, t); //ms size
sum += t;
}
ms = max(ms, tot - sum);
if (ms <= tot / 2)
wc = u;
return sum;
}
int get(int a[], int kk) //
{
sort(a, a + kk);
int res = 0;
for (int i = kk - 1, j = -1; i >= 0; i--)
{
while (j + 1 < i && a[j + 1] + a[i] <= k)
j++;
j = min(j, i - 1);
res += j + 1;
}
return res;
}
int calc(int u)
{
if (st[u])
return 0; //
get_wc(u, -1, get_size(u, -1), u); // ， u
//
st[u] = true;
int res = 0;
int pt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i], qt = 0;
get_dist(j, -1, w[i], qt); //
res -= get(q, qt); //?
for (int kk = 0; kk < qt; kk++) //
{
if (q[kk] <= k)
res++;
p[pt++] = q[kk];
}
}
res += get(p, pt);
for (int i = h[u]; ~i; i = ne[i])
res += calc(e[i]);
return res;
}
void init()
{
init_h;
memset(st, 0, sizeof st);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int StartTime = clock();
#endif
while (scanf("%d%d", &n, &k), n || k)
{
init();
for (int i = 0; i < n - 1; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c), add(b, a, c);
}
printf("%d
", calc(0));
}
#ifndef ONLINE_JUDGE
printf("Run_Time = %d ms
", clock() - StartTime);
#endif
return 0;
}
2.Acwing. ウェイト値
トランスファゲート
に言及
長さがkに等しい経路の中で、点数の最も少ない点数を求めます.
ぶんせき
ツリーの統計的な答えの問題で、大きな問題をサブ問題に分割できます.点分治で作ることができます.
コード#コード#
#include
'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)
//---------------
// k ：
//1.
//2.
//3.
const int N = 2e5 + 10;
int n, k;
int h[N], e[N << 1], w[N << 1], ne[N << 1], idx;
int f[1000010]; //f ， dp。f[i] i ， inf，
int ans = INF;
bool st[N];
PII q[N], p[N]; // ？
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int get_size(int u, int fa) //
{
if (st[u])
return 0;
int res = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int t = e[i];
if (t == fa)
continue;
res += get_size(t, u);
}
return res;
}
int get_wc(int u, int fa, int tot, int &wc) // ，
{
if (st[u])
return 0;
int sum = 1, ms = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int t = e[i];
if (t == fa)
continue;
int tt = get_wc(t, u, tot, wc);
sum += tt;
ms = max(ms, tt);
}
ms = max(ms, tot - sum);
if (ms <= tot / 2)
wc = u;
return sum;
}
void get_dist(int u, int fa, int dist, int bian, int &top)
{
if (st[u] || dist > k)
return;
q[top++] = {
dist, bian};
for (int i = h[u]; ~i; i = ne[i])
{
int t = e[i];
if (t == fa)
continue;
get_dist(t, u, dist + w[i], bian + 1, top);
}
}
void calc(int u)
{
if (st[u])
return;
get_wc(u, -1, get_size(u, -1), u); //
st[u] = true;
//
int pt = 0;
for (int i = h[u]; ~i; i = ne[i])
{
int t = e[i], qt = 0;
get_dist(t, u, w[i], 1, qt); // ， q
fir(j, 0, qt - 1)
{
auto &tt = q[j];
//
if (tt.first == k)
ans = min(ans, tt.second);
//
ans = min(ans, f[k - tt.first] + tt.second);
p[pt++] = tt;
}
fir(j, 0, qt - 1) // q f ,
{
auto &tt = q[j];
f[tt.first] = min(f[tt.first], tt.second);
}
}
// p ， f inf （memset ）
fir(i, 0, pt - 1)
{
f[p[i].first] = INF;
}
//
for (int i = h[u]; ~i; i = ne[i])
{
calc(e[i]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int StartTime = clock();
#endif
init_h;
scanf("%d%d", &n, &k);
fir(i, 1, n - 1)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
memset(f, 0x3f, sizeof f);
calc(0);
if (ans == INF)
ans = -1;
printf("%d
", ans);
#ifndef ONLINE_JUDGE
printf("Run_Time = %d ms
", clock() - StartTime);
#endif
return 0;
}
小結:点分治は木の上の答えを処理するために用いられ、1.統計的な答えが必要な問題.2.サブ問題に変換できる問題.点分治は特に優れたアルゴリズムではないような気がします.各層では,関連情報を再処理し,答えが異なるサブツリーにある場合&&答えがその層の重心に押されている場合を処理する.しかし重心の性質:全体の時間複雑度はlog級であるため,再帰関数が熟練した後,符号量も大きくない.