首页 > 其他分享 >换根

换根

时间:2023-07-19 21:44:53浏览次数:34  
标签:dad cnt int ed sum son 换根

换根

用于解决树上假设每个点均为根的问题

思路:跑两遍dfs,第一遍假设一个节点为根,第二遍根据上一遍跑的尝试计算父节点的贡献并得出所有节点为根的情况

第二遍dfs一般思路为:如果为根节点,那么记录,否则将父节点纳入考虑中

在遍历所有子节点前记录现在的数据,要遍历那个子节点就取消该子节点的数据对该数据的影响再继续dfs,然后还原到原来的数据

P3478 [POI2008] STA-Station

题意:以一个节点为根使得所有节点深度之和最大

思路:维护以该节点为子节点的节点数量与总深度

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

const int N = 1e6 + 10;

vector<int> ed[N];

ll cnt[N],sumdep[N];

void dfs1(int son,int dad){
	cnt[son] = 1;
	for(auto v:ed[son]){
		if(v == dad) continue;
		dfs1(v,son);
		cnt[son] += cnt[v];
		sumdep[son] += cnt[v] + sumdep[v];
	}
}

pair<ll,ll> ans;

void dfs2(int son,int dad){
	if(son == 1){
		ans = {sumdep[1],1};
	}else{
		sumdep[son] += cnt[dad] + sumdep[dad];
		cnt[son] += cnt[dad];
		if(sumdep[son] > ans.first)
			ans = {sumdep[son],son};
	}
	ll rescnt = cnt[son],ressum = sumdep[son];
	for(auto v:ed[son]){
		if(v == dad) continue;
		cnt[son] -= cnt[v];
		sumdep[son] -= cnt[v] + sumdep[v];
		dfs2(v,son);
		cnt[son] = rescnt;
		sumdep[son] = ressum;
	}
}

int main(){
	IOS
	int n;cin >> n;
	for(int i = 1;i < n;i++){
		int u,v;cin >> u >> v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	dfs1(1,1);
	dfs2(1,1);
	cout << ans.second << endl;
}

P2986 [USACO10MAR] Great Cow Gathering G

题意:n个牛棚,n-1条路,每个牛棚有\(C_i\)只牛,不方便的程度为\(\sum _{i-1}^nC_idis_i\),\(dis_i\)为根到该点的距离,问最小的不方便值为多少

思路:维护牛的数量,总不方便值

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

const int N = 1e5 + 10;
ll cnt[N],sum[N],c[N];

vector<pair<int,int>> ed[N];

void dfs1(int son,int dad){
	cnt[son] += c[son];
	for(auto pa:ed[son]){
		int v = pa.first,dis = pa.second;
		if(v == dad) continue;
		dfs1(v,son);
		cnt[son] += cnt[v];
		sum[son] += sum[v] + cnt[v] * dis;
	}
}

ll ans;

void dfs2(int son,int dad,ll dis){
	if(son == 1){
		ans = sum[son];
	}else{
		cnt[son] += cnt[dad];
		sum[son] += cnt[dad] * dis + sum[dad];
		ans = min(sum[son],ans);
	}
	ll rescnt = cnt[son],ressum = sum[son];
	for(auto pa:ed[son]){
		int v = pa.first,_dis = pa.second;
		if(v == dad) continue;
		cnt[son] -= cnt[v];
		sum[son] -= cnt[v] * _dis + sum[v];
		dfs2(v,son,_dis);
		cnt[son] = rescnt;
		sum[son] = ressum;
	}
}

int main(){
	IOS
	int n;cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> c[i];
	for(int i = 1;i < n;i++){
		int a,b,l;cin >> a >> b >> l;
		ed[a].push_back({b,l});
		ed[b].push_back({a,l});
	}
	dfs1(1,1);
	dfs2(1,1,0);
	cout << ans << endl;
}

E. Tree Painting

题意:给定一棵n个点的树 初始全是白点

要求你做n步操作,每一次选定一个与一个黑点相隔一条边的白点,将它染成黑点,然后获得该白点被染色前所在的白色联通块大小的权值。

第一次操作可以任意选点。

求可获得的最大权值

思路:维护数量与答案

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

const int N = 2e5 + 10;
ll cnt[N],sum[N];
vector<int> ed[N];

ll ans;
void dfs1(int son,int dad){
	cnt[son] = 1;
	for(auto v:ed[son]){
		if(v == dad) continue;
		dfs1(v,son);
		cnt[son] += cnt[v];
		sum[son] += cnt[v] + sum[v];
	}
}

void dfs2(int son,int dad){
	if(son == 1){
		ans = sum[1];
	}else{
		sum[son] += cnt[dad] + sum[dad];
		cnt[son] += cnt[dad];
		ans = max(sum[son],ans);
	}
	ll ressum = sum[son],rescnt = cnt[son];
	for(auto v:ed[son]){
		if(v == dad) continue;
		sum[son] -= sum[v] + cnt[v];
		cnt[son] -= cnt[v];
		dfs2(v,son);
		sum[son] = ressum;
		cnt[son] = rescnt;
	}
}

int main(){
	IOS
	int n;cin >> n;
	for(int i = 1;i < n;i++){
		int u,v;cin >> u >> v;
		ed[u].push_back(v);
		ed[v].push_back(u);
	}
	dfs1(1,1);
	dfs2(1,1);
	cout << ans + n << endl;
}

C. Centroids

等我水

标签:dad,cnt,int,ed,sum,son,换根
From: https://www.cnblogs.com/xxcdsg/p/17566859.html

相关文章

  • 230707 // 换根复习续
    A.叶子的染色http://222.180.160.110:1024/contest/3824/problem/1不难发现题目非常难以看懂。其实题目的意思是,\(1\simn\)一定是叶子节点(就不能明说吗)。那么问题来了,这是一棵无根树,那么我们所选取的根会对答案造成影响吗?由于\(c_u\)给定的是根节点到\(u\)路径上最后......
  • 230706 // 换根 DP 复习
    菌:园什是我笋子元首:我是你打野我:元首耳朵得治G.求树的重心http://222.180.160.110:1024/contest/3744/problem/7我们知道,重心的定义是,将其切除后,每个连通块的大小不超过\(\dfracn2\)。连通块分为其子树和整棵树减去该结点引导的子树,所以我们记录size,在每次搜索结束后......
  • CF708C Centroids 换根dp
    CF708CCentroids一道换根DP。我们可以先找出树的一个重心,那么对于其他所有不是重心的点,它不能成为重心时因为它父亲的那一支节点数大于一半,而可以改造成功,则意味着可以在他父亲那一支里,可以找到子树u,使$siz[u]\len/2$&&$siz[fa]-siz[u]\len/2$。简而言之,就是对于每个......
  • Longest Path (牛客多校) (换根DP+斜率优化)
    换根dp:第一次dfs处理儿子点的权值第二次dfs处理父亲点,和兄弟节点的权值处理兄弟节点的时候,利用父亲节点统一处理,利用stl存储斜率优化:为什么会用到斜率优化:在遇到转移式子是fixfj的时候,不是分开的,(分开的,直接用单调队列处理)(通常会遇到平方式子)把......
  • 换根DP
    换根法思路:自下而上递推;自上而下递推。P3478[POI2008]STA-Station首先使用\(\text{dfs}\)求出以每个节点\(u\)为根的子树大小\(s[u]\)。然后我们设\(f[i]\)为以\(i\)为根时所有节点的深度之和,\(j\)为\(i\)的子节点。那么对于所有\(j\)的子节点,深度都减\(......
  • 换根问题
    例题:P3979遥远的国度这是个树上查询子树信息问题。一开始一定会给出一个根,接下来会给出一些换根操作(就是让某个节点作为新的树根),在某个换根操作以后,接下来的操作(就是查询)会按照刚才缓过来的根进行查询。因为不论换根前后,这棵树的整体结构形态不变,变的只是节点与节点之间的父子关......
  • CF708C Centroids(换根dp)
    题意:给定一颗树,你有一次将树改造的机会,改造的意思是删去一条边,再加入一条边,保证改造后还是一棵树。请问有多少点可以通过改造,成为这颗树的重心?(如果以某个点为根,每个子树的大小都不大于\(\dfrac{n}{2}\),则称某个点为重心)思路:是今天遇到的一道有意思的换根dp呃呃。从题意来看......
  • 换根 DP 板子
    以前一直以为这玩意是随机应变的。结果还真能总结出板子。当然也有一定的局限性,比如\(dp\)值必须\(O(1)\)算。但不影响正常使用。ins:向\(k\)的子树信息中插入/删除\(nx\)的子树信息。这里的子树在dfs1中是指以\(1\)为根的子树;dfs2中是指以\(k\)为根。recalc......
  • 换根dp
    给定一棵树,树中包含nn个结点(编号11~nn)和n−1n−1条无向边,每条边都有一个权值。请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。输入格式第一行包含整数nn。接下来n−1n−1行,每行包含三个整数ai,bi,ciai,bi,ci,表示点aiai和bibi之间存在一条权值为ci......
  • 洛谷 P5642 - 人造情感(换根 dp)
    想起来很轻松,写起来很酸爽的套路题。默认以\(1\)为根。先考虑怎么算单个\(f(u,v)\),我们定义一个连通块的权值为从该连通块中选出若干条点不相交的路径,选出的路径的权值之和的最大值。那么显然\(f(u,v)\)就是整棵树的权值\(-\)挖掉\((u,v)\)这条路径后各个连通块的权值之......