CodeM资格赛 Round A 最长树链

按照题解的做法，对于每一个质约数分别进行讨论最长链就行
对于每一个数的质约数可是比logn还要小的

比赛的时候没人写，我也没看 = =，可惜了，不过我当时对于复杂度的把握也不大啊

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
#define MP(x, y) make_pair(x, y)
#define lson l,m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;struct Node{
    int to, nx;
}E[N*2];
int head[N], tot;
void add(int fr, int to) {
    E[tot].to = to; E[tot].nx = head[fr]; head[fr] = tot ++;
}
int vis[N]; int nw; int divisor;int val[N];
int Prime[N];
int Isprime[N]; int cnt;
int dis[N];
int ans;map<int, vector<int> > mp;
map<int, vector<int> > ::iterator it;void dfs(int x) {
    dis[x] = 1;
    int maxx = 0, Maxx = 0;
    for(int i = head[x]; ~i; i = E[i].nx) {
        int y = E[i].to;
        if(vis[y] == nw || val[y] % divisor) continue;
        vis[y] = nw;
        dfs(y);
        if(dis[y] > Maxx) maxx = Maxx, Maxx = dis[y];
        else if(dis[y] > maxx) maxx = dis[y];
    }
    ans = max(maxx + Maxx + 1, ans);
    dis[x] = Maxx + 1;
}
void solve(int x) {
    divisor = x;    //  printf("%d: ",x); for(int i = 0; i < mp[x].size(); ++i) printf("%d ", mp[x][i]); printf("\n");
    ++nw;
    for(int i = 0; i < mp[x].size(); ++i) {
        int y = mp[x][i];
        if(vis[y] != nw) {
            vis[y] = nw;
            dfs(y);
            //          printf("hh\n");
        }
    }
}
int main() {
    int n;
    cnt = 0;
    for(int i = 2; i < N; ++i) {
        if(!Prime[i]) {
            Isprime[++cnt] = i;
            for(int j = 2*i; j < N; j += i) {
                Prime[j] ++;
            }
        }
    }
    //  for(int i = 1; i <= 10; ++i) printf("%d ", Isprime[i]); printf("\n");
    while(~scanf("%d", &n)) {
        mp.clear();
        nw = 0; memset(vis, 0, sizeof(vis));
        memset(head, -1, sizeof(head)); tot = 0;        for(int i = 1; i < n; ++i) {
            int a, b; scanf("%d %d", &a, &b);
            add(a, b); add(b, a);
        }
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &val[i]);
            int tt = val[i];
            //  printf("%d ", val[i]);
            for(int j = 1; 1ll*Isprime[j] * Isprime[j] <= tt; ++j) {
                if(tt % Isprime[j] == 0) {
                    mp[Isprime[j]].push_back(i);
                    while(tt % Isprime[j] == 0) {
                        tt /= Isprime[j];
                    }
                }
            }
            if(tt != 1) {
                mp[tt].push_back(i);
            }
        }
        //  printf("hh\n");         ans = -1;
        for(it = mp.begin(); it != mp.end(); ++it) {
            solve(it->first);
        }        printf("%d\n", ans);
    }
    return 0;
}