2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛81

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛81 [2021/05/22 11:16]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:牛客练习赛81 [2021/05/22 11:29] (当前版本)
jxm2001
@@ 行 74: / 行 74: @@
 </code>
 </hidden>
+===== D-小Q与树 =====
+==== 题意 ====
+给定一棵点权树，求 $\sum_{u=1}^n\sum_{v=1}^n\min (a_u,a_v)\text{dis}(u,v)$。
+==== 题解 ====
+点分治，然后统计路径贡献。定义偏序关系 $P(u,v)$ 表示 $a_u\gt a_v$ 或 $a_u = a_v,u\gt v$。
+每次点分治时，对每个点 $u$，统计 $\sum_{P(u,v)}a_v\text{dis}(a_v,rt)+\text{dis}(a_u,rt)\sum_{P(u,v)}a_v$ 即可。
+时间复杂度 $O(n\log^2 n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,Mod=998244353;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+struct Node{
+	int s,dis;
+	Node(int s=0,int dis=0):s(s),dis(dis){}
+	void operator += (const Node &b){
+		s=s+b.s;
+		if(s>=Mod)s-=Mod;
+		dis=dis+b.dis;
+		if(dis>=Mod)dis-=Mod;
+	}
+	bool operator < (const Node &b)const{
+		return false;
+	}
+};
+int a[MAXN],sz[MAXN],mson[MAXN],tot_sz,root,root_sz,ans;
+bool vis[MAXN];
+vector<pair<int,Node> >sd;
+typedef vector<pair<int,Node> >::iterator iter;
+void dfs1(int u,int fa,int dis){
+	sd.push_back(make_pair(a[u],Node(1LL*a[u]*dis%Mod,dis)));
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		dfs1(v,u,dis+1);
+	}
+}
+void dfs2(int u,int fa,int n,int f){
+	iter it=lower_bound(sd.begin(),sd.end(),make_pair(a[u],Node()));
+	Node cur=(it==sd.begin())?Node(0,0):(--it)->second;
+	ans=(ans+(cur.s+1LL*a[u]*(n-cur.dis))*f)%Mod;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		dfs2(v,u,n,f);
+	}
+}
+void cal(int u,int dis,int f){
+	sd.clear();
+	dfs1(u,0,dis);
+	sort(sd.begin(),sd.end());
+	iter it=sd.begin();
+	++it;
+	for(;it!=sd.end();it++){
+		iter p=--it;
+		++it;
+		it->second+=p->second;
+	}
+	dfs2(u,0,(--it)->second.dis,f);
+}
+void query(int u){
+	cal(u,0,1);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(!vis[v])
+		cal(v,1,-1);
+	}
+}
+void find_root(int u,int fa){
+	sz[u]=1;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		find_root(v,u);
+		sz[u]+=sz[v];
+		mson[u]=max(mson[u],sz[v]);
+	}
+	mson[u]=max(mson[u],tot_sz-sz[u]);
+	if(mson[u]<root_sz){
+		root=u;
+		root_sz=mson[u];
+	}
+}
+void solve(int u){
+	int cur_sz=tot_sz;
+	vis[u]=true;query(u);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v])
+		continue;
+		tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];root_sz=MAXN;
+		find_root(v,u);
+		solve(root);
+	}
+}
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	tot_sz=n,root_sz=MAXN;
+	find_root(1,0);
+	solve(root);
+	enter((ans+Mod)%Mod*2%Mod);
+	return 0;
+}
+</code>
+</hidden>

2020-2021/teams/legal_string/jxm2001/contest/牛客练习赛81.1621653370.txt.gz · 最后更改: 2021/05/22 11:16 由 jxm2001