刷题记（树的直径 - I）

树的直径 - I

BB

Today orz jjdl！

Introduction

本文主要涉及树的直径的求法

树的直径：

取树上任意一点，跑DFS(BFS)得到最远的某一点u
用点u再次跑DFS(BFS)，得到的最远距离即为树的直径

Cow Marathon - POJ 1985

Link
https://cn.vjudge.net/problem/POJ-1985
Description
给定一棵带权树，问树上最远的两个点的距离是多少
Sample Input

Sample Output

Solution：树的直径

#include <cstdio>
#include <algorithm>
#include <cstring>
//#define __DEBUG
using namespace std;
const int N = 4e4 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;

struct edge{
    int v, w, nxt;
};
int sum[N], maxsum[N], val[N], head[N], tot;
edge e[N << 1];
bool used[N];

inline void init() {
    memset(head, -1, sizeof(head));
}

inline void addEdge(int u, int v, int w) {
    e[tot] = edge{v, w, head[u]};
    head[u] = tot++;
}

void dfs1(int u, int d, int& ansu, int& ansd) {
    if(d > ansd) {
        ansd = d;
        ansu = u;
    }
    used[u] = true;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(used[v]) {
            continue;
        }

        dfs1(v, d + e[i].w, ansu, ansd);
    }
}

void dfs2(int u, int pre, int d, int& ansd) {
    ansd = max(ansd, d);
    used[u] = true;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(used[v]) {
            continue;
        }

        dfs2(v, u, d + e[i].w, ansd);
    }
}

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        init();
        while(m--) {
            int u, v, w;
            char tmp[2];
            scanf("%d%d%d%s", &u, &v, &w, tmp);
            addEdge(u, v, w);
            addEdge(v, u, w);
        }

        int ansu = -1, ansd = 0;
        memset(used, false, sizeof(used));
        dfs1(1, 0, ansu, ansd);

        memset(used, false, sizeof(used));
        dfs2(ansu, -1, 0, ansd);

        printf("%d\n", ansd);
    }
}

GCD Counting CodeForces - 1101D

Link
https://cn.vjudge.net/problem/CodeForces-1101D
Description
给定一棵树，求gcd(... > 1)的最长链
Sample Input

Sample Output

1
2
0

Solution 1：树的直径 + 分解质因数 (1107 ms)
考虑到范围只有2e5，质因数个数不会很多，可以以每一个数的质因数跑与他有相同质因数的相邻的节点
为了避免重复计算，使用unordered_set标记每一个数分别被哪个质因子搜素过
跑的时候跑树的直径，取最大即是答案

#include <bits/stdc++.h>
//#define __DEBUG
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;


struct edge {
    int v, nxt;
};
bool isprime[N];
vector<int> prime;
int head[N], tot;
edge e[N << 1];

unordered_set<int> st[N], used[N];

inline void init() {
    for(int i = 0; i < N; i++) {
        st[i].clear();
        used[i].clear();
    }
    memset(head, -1, sizeof(head));
    tot = 0;

    memset(isprime, true, sizeof(isprime));
    for(int i = 2; i < N; i++) {
        if(isprime[i]) {
            prime.emplace_back(i);
        }
        for(int j = 0; j < (int)prime.size() && i * prime[j] < N; j++) {
            isprime[i * prime[j]] = false;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

inline void addEdge(int u, int v) {
    e[tot] = edge{v, head[u]};
    head[u] = tot++;
}

inline void deposit(int idx, int val) {
    for(int pr : prime) {
        if(pr > sqrt(val)) {
            break;
        }

        if(val % pr == 0) {
            st[idx].emplace(pr);
            while(val % pr == 0) {
                val /= pr;
            }
        }
    }

    if(val != 1) {
        st[idx].emplace(val);
    }
}

void dfs1(int u, int d, int k, int& ansu, int& ansd) {
    if(d > ansd) {
        ansd = d;
        ansu = u;
    }
    used[u].emplace(k);
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(used[v].count(k) || st[v].count(k) == 0) {
            continue;
        }

        dfs1(v, d + 1, k, ansu, ansd);
    }
}

void dfs2(int u, int pre, int d, int k, int& ansd) {
    ansd = max(ansd, d);
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == pre || st[v].count(k) == 0) {
            continue;
        }

        dfs2(v, u, d + 1, k, ansd);
    }
}

int solve(int n) {
    int ret = 0;
    for(int u = 1; u <= n; u++) {
        for(int k : st[u]) {
            if(used[u].count(k) || st[u].count(k) == 0) {
                continue;
            }

            int ansu = -1, ansd = 0;
            dfs1(u, 1, k, ansu, ansd);

            ansd = 0;
            dfs2(ansu, -1, 1, k, ansd);

            ret = max(ret, ansd);
        }
    }

    return ret;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        init();
        for(int i = 1; i <= n; i++) {
            int tmp;
            scanf("%d", &tmp);
            deposit(i, tmp);
        }
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }

        printf("%d\n", solve(n));
    }
}

Solution 2：树分治 (312 ms)
对于一个节点，树的最长链只可能完全在其子树内，或其在链上
前者可以递归解决，后者可以暴力计算与其相连节点若包括其在内的在子树中的最长链，排序后取至多两条最大的解决
因此明显是分治问题，使用树分治解决
（没想到这么快 = =||）

#include <bits/stdc++.h>
//#define __DEBUG
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;

struct edge{
    int v, nxt;
};
int sum[N], maxsum[N], val[N], head[N], tot;
edge e[N << 1];
bool used[N];

inline void init() {
    memset(head, -1, sizeof(head));
}

inline void addEdge(int u, int v) {
    e[tot] = edge{v, head[u]};
    head[u] = tot++;
}

inline int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}


void getRoot(int u, int pre, int size, int& rt) {
    sum[u] = 1, maxsum[u] = 0;
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(v == pre || used[v]) {
            continue;
        }

        getRoot(v, u, size, rt);
        sum[u] += sum[v];
        maxsum[u] = max(maxsum[u], sum[v]);
    }
    maxsum[u] = max(maxsum[u], size - sum[u]);
    if(rt == -1 || maxsum[u] < maxsum[rt]) {
        rt = u;
    }
}

void getMaxDis(int u, int pre, int d, int k, int& ansd) {
    ansd = max(ansd, d);
    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v, nk = gcd(k, val[v]);
        if(v == pre || used[v] || nk == 1) {
            continue;
        }

        getMaxDis(v, u, d + 1, nk, ansd);
    }
}

int dfs(int u) {
    int ret = 0;
    used[u] = true;
    vector<int> vec;

    for(int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if(used[v]) {
            continue;
        }

        int nk = gcd(val[u], val[v]);
        if(nk > 1) {
            int ansd = 1;
            getMaxDis(v, u, 1, nk, ansd);
            vec.push_back(ansd);
        }

        int rt = -1;
        getRoot(v, u, sum[v], rt);
        ret = max(ret, dfs(rt));
    }
    sort(vec.begin(), vec.end(), greater<int>());
    vec.emplace_back(0);
    vec.emplace_back(0);
    ret = max(ret, vec[0] + vec[1] + (val[u] > 1));
    return ret;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        init();
        for(int i = 1; i <= n; i++) {
            scanf("%d", &val[i]);
        }
        for(int i = 1; i <= n - 1; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }

        int rt = -1;
        getRoot(1, -1, n, rt);
        printf("%d\n", dfs(rt));
    }
}