LuoGuP1351联合权值

末蓝、 2023-06-02 11:59 1阅读 0赞

[LuoGuP1351联合权值][LuoGuP1351]  
并不是很难的题目.  
你考虑枚举中间点,然后所有与它相连的点都满足形成权值的条件.  
所以我们就直接枚举中间点,取权值最大的两个相乘更新答案.  
然后统计所有和它相连的点的权值和,每次统计总权值的时候加上(相连的点的权值和-它自身的权值)\*它自身的权值即可.

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i) #define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::queue ; using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } const int mod = 1e4 + 7 ; const int N = 2e5 + 100 ; vector < int > G[N] ; int n , v[N] , sum[N] ; int maxn , ans ; inline bool cmp (int a , int b) { return v[a] > v[b] ; } signed main (int argc , char * argv[]) { n = rint () ; rep ( i , 2 , n ) { int u = rint () , v = rint () ; G[u].pb ( v ) ; G[v].pb ( u ) ; } rep ( i , 1 , n ) v[i] = rint () ; rep ( i , 1 , n ) sort ( G[i].begin () , G[i].end () , cmp ) ; rep ( i , 1 , n ) { if ( (int)G[i].size () < 2 ) continue ; int sum = 0 ; for (int j = 0 ; j < (int)G[i].size () ; ++ j) sum += v[G[i][j]] ; maxn = max ( maxn , v[G[i][0]] * v[G[i][1]] ) ; for (int j = 0 ; j < (int)G[i].size () ; ++ j) { int k = G[i][j] , m = (int)G[i].size () ; ans = ( ans + v[k] * ( sum - v[k] ) % mod ) % mod ; } } printf ("%lld %lld\n" , maxn , ans ) ; system ("pause") ; return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11507976.html

[LuoGuP1351]: https://www.luogu.org/problem/P1351