B题本机DEV测试和牛客在线测试结果不一样
code:
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int MAXN = 5e5 + 17; int Next[MAXN],go[MAXN],head[MAXN],tot; int father[MAXN],seg[MAXN],rev[MAXN],top[MAXN],size[MAXN],son[MAXN],dep[MAXN]; int maxn[MAXN],res[MAXN],val[MAXN]; void add(int u,int v) { Next[++tot] = head[u]; go[tot] = v; head[u] = tot; } void dfs1(int u,int F) { size[u] = 1; father[u] = F; dep[u] = dep[F] + 1; int v; for(int i = head[u];i;i = Next[i]) { v = go[i]; if(v == F)continue; dfs1(v,u); size[u] += size[v]; if(size[son[u]] < size[v])son[u] = v; } } void dfs2(int u,int F) { if(son[u]) { seg[0]++; seg[son[u]] = seg[0]; rev[seg[0]] = son[u]; top[son[u]] = top[u]; dfs2(son[u],u); } int v; for(int i = head[u];i;i = Next[i]) { v = go[i]; if(v == F)continue; if(!top[v]) { top[v] = v; seg[0]++; seg[v] = seg[0]; rev[seg[0]] = v; dfs2(v,u); } } } int check(int u,int v) { int fu = top[u]; int fv = top[v]; while(fu != fv) { if(dep[fu] < dep[fv])swap(u,v),swap(fu,fv); u = father[fu]; fu = top[u]; } if(dep[u] < dep[v])swap(u,v); return v; } int getgcd(int a,int b) { if(b == 0)return a; else getgcd(b,a % b); } int main() { memset(maxn,0,sizeof(maxn)); memset(res,0,sizeof(res)); int n,a,b; cin >> n; for(int i = 1;i <= n - 1;i += 1) { cin >> a >> b; add(a,b); add(b,a); } for(int i = 1;i <= n;i += 1) cin >> val[i]; dfs1(1,0); top[1] = 1; dfs2(1,0); int s,w; for(int i = 1;i <= n;i += 1) for(int j = i + 1;j <= n;j += 1) { s = check(i,j); w = getgcd(val[i],val[j]); if(maxn[s] < w) { maxn[s] = w; res[s] = 0; } if(maxn[s] == w)res[s]++; } for(int i = 1;i <= n;i += 1) cout << maxn[i] << ' ' << res[i] << endl; return 0; }