【树的直径】CF863 div3 F

骑猪看日落 2024-03-22 09:06 90阅读 0赞

**又是关于直径的问题**

**感觉这个思维难度不高啊 ，知道它的性质大概就能想出来做法了**

**但是我没做出来，感觉树的问题还是做的少了**

[Problem - F - Codeforces][]

题意：

给定一个无根树，每次操作可以把根换到相邻的结点，花费为c，边与边之间距离为k，收益为树的最长链-总花费，问最大收益是多少

![b38afa0092c14a22a9fec000eaad6ed1.png][]

思路：

去看看有什么特殊性质：

1.操作：把根换成**相邻**结点

2.收益和**最长链**有关

考虑最长链：对于一个结点，能延伸的最长链一定是该结点到直径的某一个端点，因此肯定要把直径求出来

然后去看操作，它说**相邻**，相邻这个特殊条件很重要，这意味着花费我们可以O(1)计算，只需BFS即可

所以做法就是，先求出树的直径，再去BFS预处理，然后枚举所有结点，对于一个结点的最长链可以O(1)计算，花费也可以O(1)计算，复杂度就是O(n)的

Code：

注：这个直径的写法很帅啊，想把它塞进板子里

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    struct ty{
    	int to,next;
    }edge[mxe<<2];
    
    int n,k,c,u,v,tot=0;
    int head[mxn];
    
    void add(int u,int v){
    	edge[tot].to=v;
    	edge[tot].next=head[u];
    	head[u]=tot++;
    } 
    void G_init(){
    	tot=0;
    	for(int i=0;i<=n;i++){
    		head[i]=-1;
    	}
    }
    vector<int> bfs(int x){
    	vector<int> d(n+1,-1);
    	queue<int> q;
    	q.push(x);
    	d[x]=0;
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		for(int i=head[u];~i;i=edge[i].next){
    			if(d[edge[i].to]==-1){
    				d[edge[i].to]=d[u]+1;
    				q.push(edge[i].to);
    			}
    		}
    	}
    	return d;
    }
    void solve(){
    	cin>>n>>k>>c;
    	G_init();
    	for(int i=1;i<=n-1;i++){
    		cin>>u>>v;
    		add(u,v);
    		add(v,u);
    	}
    	auto d1=bfs(1);
    	int p=max_element(d1.begin(),d1.end())-d1.begin();
    	auto d2=bfs(p);
    	int q=max_element(d2.begin(),d2.end())-d2.begin();
    	auto d3=bfs(q);
    	int ans=-1e18;
    	for(int i=1;i<=n;i++){
    		ans=max(ans,max(d2[i],d3[i])*k-d1[i]*c);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	int __=1;cin>>__;
    	//p_init(1e7);
    	while(__--)solve();return 0;
    }

[Problem - F - Codeforces]: https://codeforces.com/contest/1822/problem/F
[b38afa0092c14a22a9fec000eaad6ed1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c09ebb0b09374705a0651528b2698036.png