BuringStraw

BuringStraw

ホームアーカイブ

点分治

#点分治76
AI 翻訳
この記事はAIを通じて中国語から日本語に翻訳されました。原文を表示
AI が生成した要約
タイトル: 点分治 日付: 2019-06-04 13:56:00 タグ: [点分治] URL名: 41 点分治は、木構造上のパス問題を解決するための手法です。特に、点間のパスの長さがkである場合の数を求めるのに使用されます。手順としては、まず重心を求めて木の層数を減らし、TLEを防ぎます。具体的な実装としては、各ノードの子木のサイズを計算し、最大の子木サイズを更新する関数が含まれています。また、深さを計算し、結果を集計するための関数も実装されています。全体的に、効率的に木構造の問題を解決するためのアルゴリズムが示されています。

点分治#

大佬がデンプンが美味しいと言っていたので、問題を解くために行きました。

image

作用#

木の上のパスの問題を求めるために使用します。

例えば、点の間のパスの長さが k であるものがいくつあるかなどです。

步骤#

  • まず重心を求めて、この木の層数が少なくなるようにし、TLE を防ぎます。

    • void getG(int p, int fa) {
    treeSize[p] = 1;//現在のノードを根とする部分木のサイズ
    sonLargest[p] = 0;//あるノードの最大の部分木のサイズ
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);//親を部分木として考えるのも一つのケース（ここに 1 を加える必要があると感じますが、他の大佬のコードには加えられていません）（影響はないようですが）
    if (sonLargest[p] < sonLargest[root]) root = p;
}

  • 次に重心から再帰的に解決します。

    • void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0);//現在のノードを根とし、左の子ノードから右の子ノードへのパスの状況を計算
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w);//重複を除く
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

    • 重複除去はおおよそこのような状況です。

      image

  • 左の子ノード —— 根 —— 右の子ノードのパスを求めます。

    • これは具体的な問題によります。

    • //これは k より短いパスを求める例です
int calc (int p, int de) {
	newd = 0;
	int ans = 0;
    getDep(p, 0, de);
    sort(dep + 1, dep + 1 + newd);
	int l = 1, r = newd;
	while (l < r) {
		if (dep[l] + dep[r] <= k) {
			ans += r - l;
			++l;
		}
		else {
			--r;
		}
	}
	return ans;
}

    • getDep は p から p の子ノードまでの距離を求めるために使用されます。

       void getDep(int p, int fa, int l) {//l は根から p までの距離
     dep[++newd] = l;
     for (int i = head[p]; i; i = e[i].nex) {
         int y = e[i].to;
         if (y !=fa && (!v[y])) {
             getDep(y, p, l + e[i].w);
         }
     }
 }

例題#

全て洛谷のものです。

P3806 【模板】点分治 1#

テンプレート問題

問い合わせをオフラインにし、calc 時に点対を二つずつ列挙し、すべての可能な結果を統計します。

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;

struct ed {
    int to,w,nex;
} e[MAXN];

int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans[10000000 + 5];
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];

void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
void calc (int p, int de, int add);

int main(void) {
    #ifndef ONLINE_JUDGE
    long _begin_time = clock();
    freopen("in.txt","r",stdin);
    freopen("out.txt", "w", stdout);
    #endif

    scanf("%d%d", &n, &m);
    sizeTot = sonLargest[0] = n;
    for (int i = 1; i < n; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        lineAdd(p1, p2, w);
        lineAdd(p2, p1, w);
    }
    getG(1, 0);
    //memset(v, 0, sizeof(v));
    solve(root);
    for(int i = 1; i <= m; ++i) {
        scanf("%d", &k);
        printf("ans[k] > 0?"AYE\n":"NAY\n");
    }

    #ifndef ONLINE_JUDGE
    long _end_time = clock();
    cout << "time = " << _end_time - _begin_time << "ms" <<endl;
    #endif
    return 0;
}

void lineAdd(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void getG(int p, int fa) {
    treeSize[p] = 1;
    sonLargest[p] = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
    if (sonLargest[p] < sonLargest[root]) root = p;
}

void getDep(int p, int fa, int l) {
    dep[++newd] = l;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y !=fa && (!v[y])) {
            getDep(y, p, l + e[i].w);
        }
    }
}

void solve(int u) {
    v[u] = 1;
    calc(u, 0, 1);
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            calc(y, e[i].w, -1);
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

void calc (int p, int de, int add) {
	newd = 0;
    getDep(p, 0, de);
    for (int i = 1; i <= newd; ++i) {
        for (int j = 1; j <= newd; ++j) {
            ans[dep[i] + dep[j]] += add;
        }
    }
}

P2634 聪聪可可#

getDep 時に dep[0] で整除を記録し、dep[1] で余りが 1 のものを記録します。。。。

calc の中での答えは dep[0] * dep[0] + dep[1] * dep[2] * 2 です。

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define clear(a) memset(a, 0, sizeof(a))
using namespace std;

const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;

struct ed {
    int to,w,nex;
} e[MAXN];

int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans;
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];

void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
int calc (int p, int de);
int gcd (int p1, int p2) {return (p2 % p1 == 0) ? p1 : gcd(p2 % p1, p1);}

int main(void) {
    #ifndef ONLINE_JUDGE
    long _begin_time = clock();
    freopen("in.txt","r",stdin);
    freopen("out.txt", "w", stdout);
    #endif
    scanf("%d", &n);
    sizeTot = sonLargest[0] = n;
    for (int i = 1; i < n; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        lineAdd(p1, p2, w);
        lineAdd(p2, p1, w);
    }
    getG(1, 0);
    solve(root);
    int fenMu = n * n;
    int g = gcd(ans, fenMu);
    printf("%d/%d\n", ans / g, fenMu / g);

    #ifndef ONLINE_JUDGE
    long _end_time = clock();
    cout << "time = " << _end_time - _begin_time << "ms" <<endl;
    #endif
    return 0;
}

void lineAdd(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void getG(int p, int fa) {
    treeSize[p] = 1;
    sonLargest[p] = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
    if (sonLargest[p] < sonLargest[root]) root = p;
}

void getDep(int p, int fa, int l) {
    ++dep[l % 3];
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y !=fa && (!v[y])) {
            getDep(y, p, (l + e[i].w) % 3);
        }
    }
}

void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0);
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w);
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

int calc (int p, int de) {
    dep[0] = dep[1] = dep[2] = 0;
    getDep(p, 0, de);
    int ans = dep[0] * dep[0] + dep[1] * dep[2] * 2;
    return ans;
}

P4178 Tree#

この問題では calc の統計時に暴力的に列挙してはいけません、さもなければ全て TLE になります。

#include<cstdio>
#include<ctime>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int MAXN=40000 * 2 + 5, INF=0x3f3f3f3f;

struct ed {
    int to,w,nex;
} e[MAXN];

int dep[MAXN];
int newp, root, sizeTot,newd;
int n, m, k;
int ans;
int head[MAXN], dist[MAXN];
int treeSize[MAXN], sonLargest[MAXN]={INF};
bool v[MAXN];

void lineAdd (int p1, int p2, int w);
void getG (int v, int fa);
void getDep (int p, int fa, int l);
void solve (int u);
int calc (int p, int de);

int main(void) {
    #ifndef ONLINE_JUDGE
    long _begin_time = clock();
    freopen("in.txt","r",stdin);
    freopen("out.txt", "w", stdout);
    #endif

    scanf("%d", &n);
    sizeTot = sonLargest[0] = n;
    for (int i = 1; i < n; ++i) {
        int p1, p2, w;
        scanf("%d%d%d", &p1, &p2, &w);
        lineAdd(p1, p2, w);
        lineAdd(p2, p1, w);
    }
    scanf("%d", &k);
    getG(1, 0);
    solve(root);
	printf("%d\n", ans);

    #ifndef ONLINE_JUDGE
    long _end_time = clock();
    cout << "time = " << _end_time - _begin_time << "ms" <<endl;
    #endif
    return 0;
}

void lineAdd(int p1, int p2, int w) {
    ++newp;
    e[newp].w = w;
    e[newp].to = p2;
    e[newp].nex = head[p1];
    head[p1] = newp;
}

void getG(int p, int fa) {
    treeSize[p] = 1;
    sonLargest[p] = 0;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y != fa && (v[y] == 0)) {
            getG(y, p);
            treeSize[p] += treeSize[y];
            sonLargest[p] = max(sonLargest[p], treeSize[y]);
        }
    }
    sonLargest[p] = max(sonLargest[p], sizeTot - treeSize[p] + 1);
    if (sonLargest[p] < sonLargest[root]) root = p;
}

void getDep(int p, int fa, int l) {
    dep[++newd] = l;
    for (int i = head[p]; i; i = e[i].nex) {
        int y = e[i].to;
        if (y !=fa && (!v[y])) {
            getDep(y, p, l + e[i].w);
        }
    }
}

void solve(int u) {
    v[u] = 1;
    ans += calc(u, 0);
    for (int i = head[u]; i; i = e[i].nex) {
        int y = e[i].to;
        if (!v[y]) {
            ans -= calc(y, e[i].w);
            sonLargest[0] = sizeTot = treeSize[u];
            root = 0;
            getG(y, 0);
            solve(root);
        }
    }
}

int calc (int p, int de) {
	newd = 0;
	int ans = 0;
    getDep(p, 0, de);
    sort(dep + 1, dep + 1 + newd);
	int l = 1, r = newd;
	while (l < r) {
		if (dep[l] + dep[r] < k) {
			ans += r - l;
			++l;
		}
		else {
			--r;
		}
	}
	return ans;
}
読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。