【Foreign】Walk [暴力]

Walk

Time Limit: 20 Sec Memory Limit: 256 MB

Description

Input

Output

Sample Input

　　3
　　1 2 3
　　1 3 9

Sample Output

　　9
　　3
　　0

HINT

Solution

　　其实吧，就是每次枚举一个d，重新构图，把权值是 d 的倍数的边加入。然后Dfs暴力求一遍直径L，显然 [1, L] 都可以用 d 更新。

　　重点是在于复杂度的证明吧，证明在上面qwq（BearChild当时不敢写qaq）。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<vector>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int n;

 int x, y, z;

 int Maxval, S[ONE];

 int Ans[ONE];

 vector <int> D[ONE], G[ONE];

 struct power

 {

         int x, y, z;

 }a[ONE];

 int get()

 {

         int res=,Q=;char c;

         while( (c=getchar())< || c> )

         if(c=='-')Q=-;

         res=c-;

         while( (c=getchar())>= && c<= )

         res=res*+c-;

         return res*Q;

 }

 void Dealiv()

 {

         for(int i = ; i <= n; i++)

         {

             int Q = sqrt(a[i].z);

             for(int j = ; j <= Q; j++)

                 if(a[i].z % j == )

                 {

                     D[j].push_back(i);

                     if(a[i].z / j != j) D[a[i].z / j].push_back(i);

                 }

         }

 }

 int vis[ONE], length, A1, Record;

 int next[ONE], first[ONE], go[ONE], tot;

 void Add(int u, int v)

 {

         next[++tot] = first[u]; first[u] = tot; go[tot] = v;

         next[++tot] = first[v]; first[v] = tot; go[tot] = u;

 }

 void Dfs1(int u, int father, int dep)

 {

         if(length < dep) {A1 = u, length = dep;}

         for(int e = first[u]; e; e = next[e])

         {

             int v = go[e];

             if(v == father || vis[v]) continue;

             Dfs1(v, u, dep + );

         }

 }

 void Dfs2(int u, int father, int dep)

 {

         vis[u] = ;

         length = max(length, dep);

         for(int e = first[u]; e; e = next[e])

         {

             int v = go[e];

             if(v == father || vis[v]) continue;

             Dfs2(v, u, dep + );

         }

 }

 int main()

 {

         n = get();

         for(int i = ; i < n; i++)

             a[i].x = get(), a[i].y = get(), a[i].z = get(), Maxval = max(Maxval, a[i].z);

         Dealiv();

         int res = ;

         for(int i = ; i <= Maxval; i++)

         {

             int len = D[i].size(), cnt = ; tot = ;

             for(int j = ; j < len; j++)

             {

                 int id = D[i][j];

                 Add(a[id].x, a[id].y);

                 S[++cnt] = a[id].x,    S[++cnt] = a[id].y;

             }

             Record = ;

             for(int j = ; j <= cnt; j++)

             if(!vis[S[j]])

             {

                 A1 = length = ; Dfs1(S[j], , );

                 length = ;    Dfs2(A1, , );

                 Record = max(Record, length);

             }

             for(int j = ; j <= cnt; j++)

                 first[S[j]] = , vis[S[j]] = ;

             Ans[Record] = i;

         }

         for(int i = n; i >= ; i--)

             Ans[i] = max(Ans[i + ], Ans[i]);

         for(int i = ; i <= n; i++)

             printf("%d\n", Ans[i]);

 }

巴特西

【Foreign】Walk [暴力]

Walk

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

Code

最新文章

热门文章