1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| #include<iostream> #include<vector> #include<cmath> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } int max(int a,int b) { if(a>b)return a; return b; } const int maxn=400005; vector<int>edges[maxn],Value[1000005]; struct Edge { int from,to,dist; } edge[maxn]; int f1[maxn],f2[maxn],f[maxn],vst[maxn],ans[maxn]; void Decompos(int id) { int x=edge[id].dist; for(int i=1; i<=sqrt(x); i++) { if(x%i==0) { Value[i].push_back(id); if(x/i!=i)Value[x/i].push_back(id); } } } void TreeDp(int Now,int father,int id) { vst[Now]=id; f[Now]=f1[Now]=f2[Now]=0; for(auto &Next:edges[Now]) { if(Next==father)continue; TreeDp(Next,Now,id); if(f1[Next]+1>f1[Now]) { f2[Now]=f1[Now]; f1[Now]=f1[Next]+1; } else if(f1[Next]+1>f2[Now])f2[Now]=f1[Next]+1; f[Now]=max(f[Now],f[Next]); } f[Now]=max(f[Now],f1[Now]+f2[Now]); } int n,Max=0; void AddEdge(int x,int y) { edges[x].push_back(y); } int main() { n=Get_Int(); for(int i=1; i<n; i++) { edge[i].from=Get_Int(); edge[i].to=Get_Int(); edge[i].dist=Get_Int(); Max=max(Max,edge[i].dist); Decompos(i); } for(int i=1; i<=Max; i++) { int len=0; for(auto &k:Value[i]) { Edge& e=edge[k]; AddEdge(e.from,e.to); AddEdge(e.to,e.from); } for(auto &k:Value[i]) { Edge& e=edge[k]; if(vst[e.from]!=i) { TreeDp(e.from,0,i); len=max(len,f[e.from]); } } ans[len]=i; for(auto &k:Value[i]) { Edge& e=edge[k]; edges[e.from].clear(); edges[e.to].clear(); } } for(int i=n-1; i>=1; i--)ans[i]=max(ans[i],ans[i+1]); for(int i=1; i<=n; i++)printf("%d\n",ans[i]); return 0; }
|