- Problem E. TeaTree
- Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
- Total Submission(s): 722 Accepted Submission(s): 255
- Problem Description
- Recently, TeaTree acquire new knoledge gcd (Greatest Common Divisor), now she want to test you.
- As we know, TeaTree is a tree and her root is node 1, she have n nodes and n-1 edge, for each node i, it has it's value v[i].
- For every two nodes i and j (i is not equal to j), they will tell their Lowest Common Ancestors (LCA) a number : gcd(v[i],v[j]).
- For each node, you have to calculate the max number that it heard. some definition:
- In graph theory and computer science, the lowest common ancestor (LCA) of two nodes u and v in a tree is the lowest (deepest) node that has both u and v as descendants, where we define each node to be a descendant of itself.
- Input
- On the first line, there is a positive integer n, which describe the number of nodes.
- Next line there are n-1 positive integers f[2] ,f[3], ..., f[n], f[i] describe the father of node i on tree.
- Next line there are n positive integers v[2] ,v[3], ..., v[n], v[i] describe the value of node i.
- n<=100000, f[i]<i, v[i]<=100000
- Output
- Your output should include n lines, for i-th line, output the max number that node i heard.
- For the nodes who heard nothing, output -1.
求树上每点的一个值
这个值 是 该点 以及它的子树所有点的 最大 gcd
- #include <iostream>
- #include <vector>
- #define rep(i,a,b) for(int i=a;i<b;i++)
- #define per(i,a,b) for(int i=a-1;i>=b;i--)
- const int MX = 1e5;
- const int MXX = 400*MX;
- using namespace std;
- int n;
- vector<int> G[MX+5],vv[MX+5];
- // init 函数 实现将 i 因数分解 (i <1e5)
- void init() {
- rep(i,1,MX+1) vv[i].push_back(1);
- rep(i,2,MX+1) {
- vv[i].push_back(i);
- for(int j=i+i;j<=MX;j+=i) vv[j].push_back(i);
- }
- // rep(i,1,MX+1) {
- // rep(j,0,vv[i].size()) {
- // printf("%d",vv[i][j]);
- // }puts("");
- // }
- }
- int root[MX+5],ls[MXX],rs[MXX],sum[MXX],rear,ans[MX];
- inline void push_up(int rt) {
- if(ls[rt] && rs[rt]) sum[rt] = max(sum[ls[rt]],sum[rs[rt]]);
- else if(ls[rt]) sum[rt] = sum[ls[rt]];
- else if(rs[rt]) sum[rt] = sum[rs[rt]];
- }
- void update(int &rt,int l,int r,int p) {
- if(rt==0) rt = ++rear;
- if(l == r) {
- sum[rt] = p;
- return ;
- }
- int m = (l+r)>>1;
- if(p <= m) update(ls[rt],l,m,p);
- else update(rs[rt],m+1,r,p);
- push_up(rt);
- }
- int merge(int rt, int prt, int &ans) {
- if(rt==0 || prt==0) return rt^prt;
- // 这里维护最大的 gcd
- if(sum[rt] == sum[prt]) ans = max(ans,sum[rt]);
- // 这里只有有因子, 就归并到 rt 上面
- if(ls[rt] | ls[prt]) ls[rt] = merge(ls[rt], ls[prt], ans);
- if(rs[rt] | rs[prt]) rs[rt] = merge(rs[rt], rs[prt], ans);
- push_up(rt);
- return rt;
- }
- void dfs(int u) {
- ans[u] = -1;
- rep(i, 0, G[u].size()) {
- int v = G[u][i];
- dfs(v);
- root[u] = merge(root[u],root[v],ans[u]);
- }
- }
- int main () {
- freopen("in.txt" ,"r",stdin);
- freopen("out.txt","w",stdout);
- init();
- scanf("%d", &n);
- // 建边
- rep(i,2,n+1) {
- int fa; scanf("%d",&fa);
- G[fa].push_back(i);
- }
- // 对每个 v[i] 建线段树
- rear=0;
- rep(i,1,n+1) {
- int x; scanf("%d", &x);
- root[i]=0;
- rep(j, 0, vv[x].size()) {
- update(root[i], 1, MX, vv[x][j]);
- }
- }
- // 暴力更新 gcd
- dfs(1);
- // 输出答案
- rep(i,1,n+1) printf("%d\n", ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2739013.html