HDU 4812 D Tree 树分治-白红宇

HDU 4812 D Tree 树分治

阅读量：4647 次

发布时间：2019-06-09

本文共 3842 字，大约阅读时间需要 12 分钟。

题意：

给出一棵树，每个节点上有个权值。要找到一对字典序最小的点对\((u, v)(u < v)\)，使得路径\(u \to v\)上所有节点权值的乘积模\(10^6 + 3\)的值为\(k\)。

分析：

比较经典的树分治。

对于分治过程中的一棵子树，我们统计两种情况：

一端为重心的路径中，到某个顶点乘积为\(k\)的路径。

两端在不同子树且过重心的路径中，乘积为\(k\)。

其他的递归到子树中去。

这里要预处理乘法逆元。

子树合并的时候，需要用到一个小技巧性的hash，参考。

#include 
    
     #include 
     
      #include 
      
       #include 
       #define MP make_pairusing namespace std;typedef long long LL;typedef pair
        
          PII;const int MOD = 1000000 + 3;const int maxn = 100000 + 10;const int INF = 0x3f3f3f3f;void read(int& x) {    x = 0;    char c = ' ';    while(c < '0' || c > '9') c = getchar();    while('0' <= c && c <= '9') {        x = x * 10 + c - '0';        c = getchar();    }}LL pow_mod(LL a, LL n) {    LL ans = 1;    while(n) {        if(n & 1) ans = ans * a % MOD;        a = a * a % MOD;        n >>= 1;    }    return ans;}int mul_mod(int a, int b) { return (LL)a * b % MOD; }int inverse(int x) { return pow_mod(x, MOD - 2); }int n, k;int a[maxn], inv[MOD];struct Edge{    int v, nxt;    Edge() {}    Edge(int v, int nxt): v(v), nxt(nxt) {}};int ecnt, head[maxn];Edge edges[maxn * 2];void AddEdge(int u, int v) {    edges[ecnt] = Edge(v, head[u]);    head[u] = ecnt++;}PII ans;bool del[maxn];int fa[maxn], sz[maxn];void dfs(int u) {    sz[u] = 1;    for(int i = head[u]; ~i; i = edges[i].nxt) {        int v = edges[i].v;        if(del[v] || v == fa[u]) continue;        fa[v] = u;        dfs(v);        sz[u] += sz[v];    }}PII findCenter(int u, int t) {    PII ans(INF, u);    int m = 0;    for(int i = head[u]; ~i; i = edges[i].nxt) {        int v = edges[i].v;        if(del[v] || v == fa[u]) continue;        ans = min(ans, findCenter(v, t));        m = max(m, sz[v]);    }    m = max(m, t - sz[u]);    ans = min(ans, MP(m, u));    return ans;}int tot, path[maxn], num[maxn];int has[MOD], id[MOD], cnt;void getproduct(int u, int p, LL prod) {    path[++tot] = prod; num[tot] = u;    for(int i = head[u]; ~i; i = edges[i].nxt) {        int v = edges[i].v;        if(del[v] || v == p) continue;        getproduct(v, u, mul_mod(prod, a[v]));    }}PII getpair(int a, int b) {    if(a < b) return MP(a, b);    else return MP(b, a);}void solve(int u) {    fa[u] = 0;    dfs(u);    int s = findCenter(u, sz[u]).second;    del[s] = true;    for(int i = head[s]; ~i; i = edges[i].nxt) {        int v = edges[i].v;        if(del[v]) continue;        solve(v);    }    cnt++;    for(int i = head[s]; ~i; i = edges[i].nxt) {        int v = edges[i].v;        if(del[v]) continue;        tot = 0;        getproduct(v, s, a[v]);        int m = mul_mod(k, inv[a[s]]);        for(int i = 1; i <= tot; i++) {            if(path[i] == m) {                PII tmp = getpair(num[i], s);                if(!ans.first || tmp < ans) ans = tmp;            }            int m2 = mul_mod(k, mul_mod(inv[path[i]], inv[a[s]]));            if(has[m2] == cnt) {                PII tmp = getpair(num[i], id[m2]);                if(!ans.first || tmp < ans) ans = tmp;            }        }        for(int i = 1; i <= tot; i++) {            if(has[path[i]] != cnt || (has[path[i]] == cnt && id[path[i]] > num[i])) {                has[path[i]] = cnt;                id[path[i]] = num[i];            }        }    }    del[s] = false;}int main(){    for(int i = 1; i < MOD; i++) inv[i] = inverse(i);    while(scanf("%d%d", &n, &k) == 2) {        for(int i = 1; i <= n; i++) read(a[i]);        ecnt = 0;        memset(head, -1, sizeof(head));        for(int i = 1; i < n; i++) {            int u, v; read(u); read(v);            AddEdge(u, v);            AddEdge(v, u);        }        ans = MP(0, 0);        memset(has, 0, sizeof(has));        cnt = 0;        solve(1);        if(!ans.first) puts("No solution");        else printf("%d %d\n", ans.first, ans.second);    }    return 0;}