题目链接: https://ac.nowcoder.com/acm/contest/2995/E
题意:
树上从 u 到 v 简单路径上所有点权中, 最大值与最小值的差值为 balance(u,v).
T 组 (T<=10),n(1<=n<=5e5),n 个 a[i](1<=a[i]<=1e9) 表示点权, n-1 个 u 和 v, 表示 u,v 两点有边连接, 保证构成一棵树
求树的 balance%1e9
样例:
答案为 179
题解:
最大值与最小值分别计算.
求最大值的方法: 从小到大将每个点与相连的点用并查集合并, 同时维护每个联通块的 size, 此时显然可以计算此点作为最大值的路径条数.
计算最小值的方法同理.
思路:
计算最大值先按点权排序
点: 4,5,6,8,9,3,10,7,1,2
点权: 2,4,5,5,5,6, 6,8,9,9
先把点4的 vis 设为 1, 表示已访问, 然后遍历所有与点4相连的已经访问的点, 未找到.
再把点5的 vis 设为 1, 表示已经访问, 然后遍历所有与点5相连的已经访问的点, 找到点4, 此时需要做如下处理:
与点4连通的联通块 (共有 size1 个点) 的最大点权都为 2, 与点5连通的联通块 (共有 size2 个点) 的最大点权都为 4,
从左边联通块任取一点, 右边联通块里任取一点, 两点之间的最大点权都为 4, 共有 size1*size2 对点, 再乘上5的点权 4, 即为这一部分的 max 值
然后联合两个块, 重新计算 size(用并查集维护), 这个块的点权是多少不重要, 因为排序是从小到大, 乘的都是大的点的点权.
计算完所有 max 点权之和后, 按倒序计算 min 点权, 相减即为答案.
附上代码 o(*~▽~*)ブ:
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=5e5+10;
- const int mod=1e9+7;
- int n,fa[maxn],size[maxn],vis[maxn];
- pair<int,int> a[maxn];
- vector<int> G[maxn];
- void init()
- {
- for(int i=1;i<=n;i++)fa[i]=i,size[i]=1;
- memset(vis,0,sizeof vis);
- }
- int get(int x)
- {
- if(fa[x]==x)return x;
- return fa[x]=get(fa[x]);
- }
- void merge(int a,int b)
- {
- a=get(a);
- b=get(b);
- if(a!=b)
- {
- fa[a]=b;
- size[b]+=size[a];
- }
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&n);
- init();
- for(int i=1;i<=n;i++)
- {
- scanf("%d",&a[i].first);
- a[i].second=i;
- G[i].clear();
- }
- for(int i=1;i<n;i++)
- {
- int u,v;
- scanf("%d%d",&u,&v);
- G[u].push_back(v);
- G[v].push_back(u);
- }
- sort(a+1,a+1+n);
- long long ans=0;
- for(int i=1;i<=n;i++)
- {
- int now=a[i].second;
- vis[now]=1;
- for(int j:G[now])
- {
- if(vis[j])
- {
- ans=(ans+(1ll*a[i].first*size[now]%mod)*size[get(j)]%mod)%mod;
- merge(j,now);
- }
- }
- }
- init();
- for(int i=n;i>=1;i--)
- {
- int now=a[i].second;
- vis[now]=1;
- for(int j:G[now])
- {
- if(vis[j])
- {
- ans=(ans-(1ll*a[i].first*size[now]%mod)*size[get(j)]%mod+mod)%mod;
- merge(j,now);
- }
- }
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
wa 了几发,
return fa[x]=get(fa[x]); 写成 return get(fa[x]);
G[i]没有写 clear()
......
nitacm 2019 校赛 E 雷顿女士与平衡树(并查集维护)
来源: http://www.bubuko.com/infodetail-3333483.html