c++ - 树的路径上所有节点的乘积

Question

我正在学习MO的算法。在那我找到了一个问题。在其中，我们必须编写一个程序来为树的n个节点获取输入n，然后n-1对u和v对表示节点u和节点v之间的连接。之后，给出n个节点值。

然后我们将问q个查询。对于每个查询，我们输入k和l来表示该树的两个节点。现在我们必须找到k和l(包括k和l)路径中所有节点的乘积。

我想使用MO的算法。 https://codeforces.com/blog/entry/43230

但是我无法编写代码。有人可以帮我这个忙吗？

的基本代码是:

int n, q;
int nxt[ N ], to[ N ], hd[ N ];

struct Que{
    int u, v, id;
} que[ N ];

void init() {
    // read how many nodes and how many queries
    cin >> n >> q;
    // read the edge of tree
    for ( int i = 1 ; i < n ; ++ i ) {
        int u, v; cin >> u >> v;
        // save the tree using adjacency list
        nxt[ i << 1 | 0 ] = hd[ u ];
        to[ i << 1 | 0 ] = v;
        hd[ u ] = i << 1 | 0;

        nxt[ i << 1 | 1 ] = hd[ v ];
        to[ i << 1 | 1 ] = u;
        hd[ v ] = i << 1 | 1;
    }

    for ( int i = 0 ; i < q ; ++ i ) {
        // read queries
        cin >> que[ i ].u >> que[ i ].v;
        que[ i ].id = i;
    }
}

int dfn[ N ], dfn_, block_id[ N ], block_;

int stk[ N ], stk_;

void dfs( int u, int f ) {
    dfn[ u ] = dfn_++;

    int saved_rbp = stk_;

    for ( int v_ = hd[ u ] ; v_ ; v_ = nxt[ v_ ] ) {
        if ( to[ v_ ] == f ) continue;
        dfs( to[ v_ ], u );
        if ( stk_ - saved_rbp < SQRT_N ) continue;
        for ( ++ block_ ; stk_ != saved_rbp ; )
             block_id[ stk[ -- stk_ ] ] = block_;
    }

    stk[ stk_ ++ ] = u;
}

bool inPath[ N ];

void SymmetricDifference( int u ) {
    if ( inPath[ u ] ) {
        // remove this edge
    } else {
        // add this edge
    }
    inPath[ u ] ^= 1;
}
void traverse( int& origin_u, int u ) {
    for ( int g = lca( origin_u, u ) ; origin_u != g ; origin_u = parent_of[ origin_u ] )
        SymmetricDifference( origin_u );
    for ( int v = u ; v != origin_u ; v = parent_of[ v ] )
        SymmetricDifference( v );
    origin_u = u;
}

void solve() {
    // construct blocks using dfs
    dfs( 1, 1 );
    while ( stk_ ) block_id[ stk[ -- stk_ ] ] = block_;
    // re-order our queries
    sort( que, que + q, [] ( const Que& x, const Que& y ) {
        return tie( block_id[ x.u ], dfn[ x.v ] ) < tie( block_id[ y.u ], dfn[ y.v ] );
    } );
    // apply mo's algorithm on tree
    int U = 1, V = 1;
    for ( int i = 0 ; i < q ; ++ i ) {
        pass( U, que[ i ].u );
        pass( V, que[ i ].v );
        // we could our answer of que[ i ].id
    }
}

Answer 1

此问题是对您共享的博客的轻微修改。

问题标签:- MO的算法，树，LCA，二进制提升，筛分，预计算，素因子

预计算:-我们只需要对seiveOfErothenesis进行一些预计算，以存储输入约束中每个元素的最高质数。然后，使用此函数，我们将输入矩阵中每个元素的所有素因数及其功效存储在另一个矩阵中。

观察:-带有约束，您可以看到每个元素几乎没有这样的素数。对于一个元素(10 ^ 6)，最多可能有7个素数因子。

修改MO算法在博客中给出:-现在，在我们的计算方法中，我们只需要维护一个映射即可存储素数的当前计数。在解决查询时添加或减去每个元素时，我们将迭代该元素的素数，然后将结果(存储因子总数)除以该素数的旧计数，然后更新该素数和将结果乘以新计数(每次加法/减法的最大值为O(7))。

复杂度:- O(T *((N + Q)* sqrt(N)* F))这里我们的F为7。 F是您的check方法的复杂性。

T-输入文件中没有测试用例。

N-输入数组的大小。

Q-查询数。

下面是上述方法在JAVA中的实现。 computePrimePowers()和check()是您感兴趣的方法。

import java.util.*;
import java.io.*;

public class Main {

    static int BLOCK_SIZE;
    static int ar[];
    static ArrayList<Integer> graph[];
    static StringBuffer sb = new StringBuffer();

    static boolean notPrime[] = new boolean[1000001];
    static int hpf[] = new int[1000001];
    static void seive(){
        notPrime[0] = true;
        notPrime[1] = true;
        for(int i = 2; i < 1000001; i++){
            if(!notPrime[i]){
                hpf[i] = i;
            for(int j = 2 * i; j < 1000001; j += i){
                notPrime[j] = true;
                hpf[j] = i;
            }
        }
    }
    }

    static long modI[] = new long[1000001];
    static void computeModI() {
        for(int i = 1; i < 1000001; i++) {
            modI[i] = pow(i, 1000000005);
        }
    }
    static long pow(long x, long y) { 
        if (y == 0) 
            return 1; 

        long p = pow(x, y / 2);
        p = (p >= 1000000007) ? p % 1000000007 : p;
        p = p * p;
        p = (p >= 1000000007) ? p % 1000000007 : p;

        if ((y & 1) == 0) 
            return p; 
        else {
            long tt = x * p;
            return (tt >= 1000000007) ? tt % 1000000007 : tt; 
        }
    }

    public static void main(String[] args) throws Exception {
        Reader s = new Reader();
        int test = s.nextInt();
        seive();
        computeModI();
        for(int ii = 0; ii < test; ii++){
            int n = s.nextInt();
            lcaTable = new int[19][n + 1];
            graph = new ArrayList[n + 1];
            arrPrimes = new int[n + 1][7][2];
            primeCnt = new int[1000001];
            visited = new int[n + 1];
            ar = new int[n + 1];
            for(int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();
            for(int i = 1; i < n; i++){
                int u = s.nextInt(), v = s.nextInt();
                graph[u].add(v);
                graph[v].add(u);
            }
            int ip = 1; while(ip <= n) ar[ip++] = s.nextInt();

            computePrimePowers();

            int q = s.nextInt();
            LVL = new int[n + 1];

            dfsTime = 0;
            dfs(1, -1);

            BLOCK_SIZE = (int) Math.sqrt(dfsTime);
            int Q[][] = new int[q][4];
            int i = 0;
            while(q-- > 0) {
                int u = s.nextInt(), v = s.nextInt();
                Q[i][0] = lca(u, v);
                if (l[u] > l[v]) {
                    int temp = u; u = v; v = temp;
                }
                if (Q[i][0] == u) {
                    Q[i][1] = l[u];
                    Q[i][2] = l[v];
                }
                else {
                    Q[i][1] = r[u]; // left at col1 in query
                    Q[i][2] = l[v]; // right at col2
                }
                Q[i][3] = i;
                i++;
            }
            Arrays.sort(Q, new Comparator<int[]>() {
                @Override
                public int compare(int[] x, int[] y) {
                    int block_x = (x[1] - 1) / (BLOCK_SIZE + 1);
                    int block_y = (y[1] - 1) / (BLOCK_SIZE + 1);
                    if(block_x != block_y)
                        return block_x - block_y;
                    return x[2] - y[2];
                }
            });
            solveQueries(Q);
        }
        System.out.println(sb);
    }

    static long res;
    private static void solveQueries(int [][] Q) {
        int M = Q.length;
        long results[] = new long[M];
        res = 1;
        int curL = Q[0][1], curR = Q[0][1] - 1;
        int i = 0;
        while(i < M){
            while (curL < Q[i][1]) check(ID[curL++]);
            while (curL > Q[i][1]) check(ID[--curL]);
            while (curR < Q[i][2]) check(ID[++curR]);
            while (curR > Q[i][2]) check(ID[curR--]);

            int u = ID[curL], v = ID[curR];

            if (Q[i][0] != u && Q[i][0] != v) check(Q[i][0]);

            results[Q[i][3]] = res;

            if (Q[i][0] != u && Q[i][0] != v) check(Q[i][0]);

            i++;
        }

        i = 0;
        while(i < M) sb.append(results[i++] + "\n");
    }

    static int visited[];
    static int primeCnt[];
    private static void check(int x) {
        if(visited[x] == 1){
            for(int i = 0; i < 7; i++) {
                int c = arrPrimes[x][i][1];
                int pp = arrPrimes[x][i][0];
                if(pp == 0) break;
                long tem = res * modI[primeCnt[pp] + 1];
                res = (tem >= 1000000007) ? tem % 1000000007 : tem;
                primeCnt[pp] -= c;
                tem = res * (primeCnt[pp] + 1);
                res = (tem >= 1000000007) ? tem % 1000000007 : tem;
            }
        }
        else if(visited[x] == 0){
            for(int i = 0; i < 7; i++) {
                int c = arrPrimes[x][i][1];
                int pp = arrPrimes[x][i][0];
                if(pp == 0) break;
                long tem = res * modI[primeCnt[pp] + 1];
                res = (tem >= 1000000007) ? tem % 1000000007 : tem;
                primeCnt[pp] += c;
                tem = res * (primeCnt[pp] + 1);
                res = (tem >= 1000000007) ? tem % 1000000007 : tem;
            }
        }
        visited[x] ^= 1;
    }

    static int arrPrimes[][][];
    static void computePrimePowers() {
        int n = arrPrimes.length;
        int i = 0;
        while(i < n) {
            int ele = ar[i];
            int k = 0;
            while(ele > 1) {
                int c = 0;
                int pp = hpf[ele];
                while(hpf[ele] == pp) {
                    c++; ele /= pp;
                }
                arrPrimes[i][k][0] = pp;
                arrPrimes[i][k][1] = c;
                k++;
            }
            i++;
        }
    }

    static int dfsTime;
    static int l[] = new int[1000001], r[] = new int[1000001], ID[] = new int[1000001], LVL[], lcaTable[][];
    static void dfs(int u, int p){
        l[u] = ++dfsTime;
        ID[dfsTime] = u;
        int i = 1;
        while(i < 19) {
            lcaTable[i][u] = lcaTable[i - 1][lcaTable[i - 1][u]];
            i++;
        }
        i = 0;
        while(i < graph[u].size()){
            int v = graph[u].get(i);
            i++;
            if (v == p) continue;
            LVL[v] = LVL[u] + 1;
            lcaTable[0][v] = u;
            dfs(v, u);
        }
        r[u] = ++dfsTime;
        ID[dfsTime] = u;
    }

    static int lca(int u, int v){
        if (LVL[u] > LVL[v]) {
            int temp = u;
            u = v; v = temp;
        }
        int i = 18;
        while(i >= 0) {
            if (LVL[v] - (1 << i) >= LVL[u]) v = lcaTable[i][v];
            i--;
        }

        if (u == v) return u;

        i = 18;
        while(i >= 0){
            if (lcaTable[i][u] != lcaTable[i][v]){
                u = lcaTable[i][u];
                v = lcaTable[i][v];
            }
            i--;
        }
        return lcaTable[0][u];
    }
}