NIT校赛-- 雷顿女士与平衡树
2024-10-06 14:25:55
题意:https://ac.nowcoder.com/acm/contest/2995/E
给你一棵树,节点有权值,让你求所有路径max-min的和。
思路:
我们计算每个点的贡献,对于一个点,当它为某条路径的最大值是,一定在一个所有值<=它的连通块里。所有我们从小到大添边合并共享(两块的大小之积,不是和)
最小值也同样处理。
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>//sprintf islower isupper
#include <cstdlib>//malloc exit strcat itoa system("cls")
#include <iostream>//pair
#include <fstream>//freopen("C:\\Users\\13606\\Desktop\\Input.txt","r",stdin);
#include <bitset>
//#include <map>
//#include<unordered_map>
#include <vector>
#include <stack>
#include <set>
#include <string.h>//strstr substr strcat
#include <string>
#include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
#include <cmath>
#include <deque>
#include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
#include <vector>//emplace_back
//#include <math.h>
#include <cassert>
#include <iomanip>
//#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
#include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
//******************
clock_t __START,__END;
double __TOTALTIME;
void _MS(){__START=clock();}
void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
//***********************
#define rint register int
#define fo(a,b,c) for(rint a=b;a<=c;++a)
#define fr(a,b,c) for(rint a=b;a>=c;--a)
#define mem(a,b) memset(a,b,sizeof(a))
#define pr printf
#define sc scanf
#define ls rt<<1
#define rs rt<<1|1
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const double E=2.718281828;
const double PI=acos(-1.0);
const ll INF=(1LL<<);
const int inf=(<<);
const double ESP=1e-;
const int mod=(int)1e9+;
const int N=(int)5e5+; int fa[N];
int SZ[N];
int Find(int x)
{
return (x==fa[x])?x:(fa[x]=Find(fa[x]));
} vector<vector<int> >G(N);
pair<ll,int> a[N];
bool vis[N]; void solve()
{
int n;
sc("%d",&n);
for(int i=;i<=n;++i)fa[i]=i,sc("%lld",&a[i].first),a[i].second=i,G[i].clear();
for(int i=;i<=n-;++i)
{
int u,v;
sc("%d%d",&u,&v);
G[v].push_back(u);
G[u].push_back(v);
}
sort(a+,a++n);
mem(vis,);
for(int i=;i<=n;++i)SZ[i]=;
ll ans=;
for(int i=;i<=n;++i)
{
int now=a[i].second;
vis[now]=;
int sz=G[now].size();
for(int j=;j<sz;++j)
{
int to=G[now][j];
if(vis[to])
{
ans=(ans+a[i].first*SZ[now]%mod*SZ[Find(to)]%mod)%mod;
SZ[now]+=SZ[Find(to)];
fa[Find(to)]=Find(now);
}
}
}
// cout<<ans<<endl;
mem(vis,);
for(int i=;i<=n;++i)SZ[i]=;
for(int i=;i<=n;++i)fa[i]=i;
for(int i=n;i>=;--i)
{
int now=a[i].second;
vis[now]=;
int sz=G[now].size();
for(int j=;j<sz;++j)
{
int to=G[now][j];
if(vis[to])
{
ans=(ans-a[i].first*SZ[now]%mod*SZ[Find(to)]%mod+mod)%mod;
SZ[now]+=SZ[Find(to)];
fa[Find(to)]=Find(now);
}
}
}
pr("%lld\n",ans);
} int main()
{
int T;
sc("%d",&T);
while(T--)solve();
return ;
} /**************************************************************************************/
最新文章
- Unity Game窗口中还原Scene窗口摄像机操作 强化版
- 高性能Linux服务器构建实战笔记
- poj1006生理周期(中国剩余定理)
- NeHe OpenGL教程 第十三课:图像字体
- c程序设计语言_习题8-4_重新实现c语言的库函数fseek(FILE*fp,longoffset,intorigin)
- 【结构型】Flyweight模式
- Palindrome Number 回文数
- Oracle 11g New 热补丁
- 解决在某些IE浏览器下字符乱码的问题
- 撸一个Android高性能日历控件,高仿魅族
- TCP基础知识 复习
- javaCV开发详解之3:收流器实现,录制流媒体服务器的rtsp/rtmp视频文件(基于javaCV-FFMPEG)
- Redis中的基本数据结构
- 进入css3动画世界(一)
- Docker最全教程之使用 Visual Studio Code玩转Docker(二十)
- 【转】visualSFM生成的bundle.rd.out文件的格式
- LCA算法总结
- docker中的安全机制
- 使用 phpStudy + VSCODE 进行 PHP 断点调试
- VM虚拟机如何和主机共享文件夹或文件