【启发式搜索】Codechef March Cook-Off 2018. Maximum Tree Path

2024-08-28 02:48:50

有点像计蒜之道里的京东的物流路径

题目描述

给定一棵 N 个节点的树，每个节点有一个正整数权值。记节点 i 的权值为 Ai。
考虑节点 u 和 v 之间的一条简单路径，记 dist(u, v) 为其长度，gcd(u, v) 为路径上所有节点
（包含 u 和 v）的权值的最大公因子。min(u, v) 为路径上所有节点的权值的最小值。
请求出所有节点对 (u, v) 中 dist(u, v) · gcd(u, v) · min(u, v) 的最大值

输入格式

输入的第一行包含一个整数 T，代表测试数据的组数。接下来是 T 组数据。
每组数据的第一行包含一个整数 N，代表树中节点的个数。接下来一行包含 N 个整数
A1, A2, . . . , AN。
接下来 N − 1 行，每行包含三个整数 u, v, w，代表节点 u 和 v 之间连有一条长度为 w 的边。

输出格式

对于每组数据，输出一行，包含一个整数，代表所求答案

数据范围

• 1 ≤ T ≤ 100
• 2 ≤ N ≤ 10^5
• 2 ≤ ∑N ≤ 10^5
• 1 ≤ Ai ≤ 10^4
• 1 ≤ u, v ≤ N
• 1 ≤ w ≤ 10^5

题目分析

常规做法

和京东的物流路径不同的是，需要在外层枚举路径的gcd，并把两端点是gcd倍数的边存下，按照端点权值的较小值排序。之后就相当于是用这些边来和那题一样做了。

参见：[树的直径] Codechef March Cook-Off 2018. Maximum Tree Path

启发式搜索

我也不知道复杂度是多少

每一次搜索时若$dia*mn*gcd(dia为直径)<ans$就return。

 #include<bits/stdc++.h>

 typedef long long ll;

 const int maxn = ;

 struct Edge

 {

     int y,val;

     Edge(int a=, int b=):y(a),val(b) {}

 }edges[maxn<<];

 long long ans;

 int tt,n,dia,S,T,a[maxn],dis[maxn];

 int edgeTot,head[maxn],nxt[maxn<<];

 int read()

 {

     char ch = getchar();

     int num = ;

     bool fl = ;

     for (; !isdigit(ch); ch=getchar())

         if (ch=='-') fl = ;

     for (; isdigit(ch); ch=getchar())

         num = (num<<)+(num<<)+ch-;

     if (fl) num = -num;

     return num;

 }

 int gcd(int a, int b){return !b?a:gcd(b, a%b);}

 void addedge(int u, int v)

 {

     int c = read();

     edges[++edgeTot] = Edge(v, c), nxt[edgeTot] = head[u], head[u] = edgeTot;

     edges[++edgeTot] = Edge(u, c), nxt[edgeTot] = head[v], head[v] = edgeTot;

 }

 void dfs(int x, int fa, int c)

 {

     dis[x] = c;

     for (int i=head[x]; i!=-; i=nxt[i])

         if (edges[i].y!=fa) dfs(edges[i].y, x, c+edges[i].val);

 }

 void fnd(int x, int fa, ll d, int g, int mn)

 {

     if (1ll*dia*g*mn <= ans) return;

     if (ans < 1ll*d*g*mn) ans = 1ll*d*g*mn;

     for (int i=head[x]; i!=-; i=nxt[i])

         if (edges[i].y!=fa)

             fnd(edges[i].y, x, d+1ll*edges[i].val, gcd(g, a[edges[i].y]), std::min(mn, a[edges[i].y]));

 }

 void fndDiameter()

 {

     S = T = , dis[] = -0x3f3f3f3f;

     dfs(, , );

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

         if (dis[S] < dis[i]) S = i;

     dfs(S, S, );

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

         if (dis[T] < dis[i])

             T = i, dia = dis[T];

     fnd(S, S, , a[S], a[S]);

 }

 int main()

 {

     tt = read();

     while (tt--)

     {

         n = read(), ans = dia = edgeTot = ;

         memset(head, -, (n+)<<);

         for (int i=; i<=n; i++) a[i] = read();

         for (int i=; i<n; i++) addedge(read(), read());

         fndDiameter();

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

             fnd(i, i, , a[i], a[i]);

         printf("%lld\n",ans);

     }

     return ;

 }

END

最新文章

热门文章