首页 > 其他分享 >暑假集训第一周专题：树

暑假集训第一周专题：树

时间：2024-07-28 17:20:01浏览次数：13  
标签：idx 第一周 int dfs st ++ 暑假 集训 he

暑假集训第一周专题：树

本专题其实还是看中对题目的阅读理解能力，dfs 实现起来很简单，主要是知道题目到底要干嘛

A. Kuro and Walking Route

题面

image-20240728163841267

输入

image-20240728163900069

输出

image-20240728163911563

思路

即所有路线减去 经过 x 到 y 的路线

由 x 到 y 的路线，包括从某些点到 x，经过一些点再到 y，从 y再到某些点

有根据题目该国家由 个城镇组成，编号从 1 到 ，还有 −1 条连接这些城镇的双向道路。可以从任何其他城镇到达每个城镇。 可以推断出是树，也就是无环，即从一个点到另一点的路径一定是固定的，所以题目说的最短路径这个说法木有用的，本来就是一条路，那么便可以画出图像

2e156d2489d37e5b3be9001072bd8c5d

所以 经过 x 到 y 的路线 等于 左边到 x 的路径数(cnt1)×右边到 y的路径数(cnt2)

由于直接求 cnt1，cnt2 不好求，不妨先求

image-20240728160054443

仅需在 dfs 之前把 st[y]设为 1走到 y 停止即可，同理也可以算出 y 的部分，两者一相加，减去总点数，即为中间点的个数，再各自减去中间点，即得到 cnt1，cnt2

所有路径数等于 n*（n-1)可以从任何其他城镇到达每个城镇

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=6e5+10;
int he[N],ne[N],e[N],idx;
int st[N];
void add(int a,int b)
{
    ne[idx]=he[a];e[idx]=b;he[a]=idx++;
}
int dfs(int x)
{
    int res=1;
    st[x]=1;
    for(int i=he[x];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])continue;
        res+=dfs(j);
    }
    return res;
}
void solve(){
    int n,x,y;cin>>n>>x>>y;
    memset(he,-1,sizeof he);
    for(int i=1;i<=n-1;++i)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    memset(st,0,sizeof st);
    st[y]=1;
    int cnt1=dfs(x);
    memset(st,0,sizeof st);
    st[x]=1;
    int cnt2=dfs(y);
    int num_ab=cnt1+cnt2-n;
    cnt1-=num_ab;
    cnt2-=num_ab;
    cout<<n*(n-1)-cnt1*cnt2;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

B. Timofey and a tree

题面

image-20240728162415169

输入

image-20240728162437674

输出

image-20240728162500457

思路

题目的意思就是，去掉顶点后的所有子图颜色都一样。

那么很明显，颜色只能顶点和他的第一代儿子颜色能不一样，其余的皆得一样，不妨先统计出所有不一样颜色的边，在统计每个节点做顶点，和其第一代儿子边不同的数目，如果一样，证明这个点可以做顶点，小于的话，这个点就不行，如果没有一个点可以即输出 NO 即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int he[N],ne[N],e[N],idx;
int c[N],st[N];
int sum,num[N];
void add(int a,int b)
{
    ne[idx]=he[a];e[idx]=b;he[a]=idx++;
}
void dfs(int u)
{
    st[u]=1;
    for(int i=he[u];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])continue;
        if(c[u]!=c[j])sum++,num[u]++,num[j]++;
        dfs(j);
    }
}
void solve(){
    int n;cin>>n;
    memset(he,-1,sizeof he);
    for(int i=1;i<=n-1;++i)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;++i)cin>>c[i];
    dfs(1);
    int res=0,p=0;
    for(int i=1;i<=n;++i)
    {
        if(num[i]==sum)res++,p=i;
    }
    if(res)cout<<"YES\n"<<p;
    else cout<<"NO\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

C. Andryusha and Colored Balloons

题面

image-20240728163120882

输入

image-20240728163133272

输出

image-20240728163144673

思路

树上三个连续点皆不能相同，不妨先找到顶点，以顶点为中心，先遍历出第一代儿子的颜色（cnt++)，即也是 k 的答案，再 dfs 遍历给第二三等等代染色，要注意的是儿子的颜色不能等于爷爷，即 dfs 要储存上一代和上上代的颜色,还有就是兄弟之间不能同色。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int he[N],ne[N],e[N],idx;
int c[N],branches[N];
int max_b=0,max_b_p=0;
void add(int a,int b)
{
    ne[idx]=he[a];e[idx]=b;he[a]=idx++;
    branches[a]++;
}
void dfs(int u,int p)
{
	int k=1;
    for(int i=he[u];~i;i=ne[i])
    {
        int j=e[i];
        if(c[j])continue;
        while(k<=max_b)
        {
        	if(k!=c[u]&&k!=c[p])
        	{
        		c[j]=k++;
        		break;
        	}
        	else k++;
        }
        dfs(j,u);
    }
}
void solve(){
    int n;cin>>n;
    memset(he,-1,sizeof he);
    for(int i=1;i<=n-1;++i)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    for(int i=1;i<=n;++i)
    {
        if(branches[i]>max_b)
        {
            max_b=branches[i];
            max_b_p=i;
        }
    }
    int cnt=1;
    max_b++;
    c[max_b_p]=cnt++;
    for(int i=he[max_b_p];~i;i=ne[i])
    {
        int j=e[i];
        c[j]=cnt++;
        dfs(j,max_b_p);
    }
    cout<<max_b<<'\n';
    for(int i=1;i<=n;++i)cout<<c[i]<<' ';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

D. Journey

题面

image-20240728163942006

输入

image-20240728164011768

输出

image-20240728164024971

思路

很简单的 dfs，没什么好说的，预处理存下每个节点的 branch（枝干）数量即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int he[N],ne[N],e[N],idx;
int st[N],branches[N];
double sum=0;
void add(int a,int b)
{
    ne[idx]=he[a];e[idx]=b;he[a]=idx++;
    branches[a]++;
}
void dfs(int u,int d,double p,bool if_first)
{
    st[u]=1;
    if(if_first)
    {
        branches[u]++;
        if_first=0;
    }
    bool flag=true;
    for(int i=he[u];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])continue;
        flag=false;
        dfs(j,d+1,(double)1/(branches[u]-1)*p,if_first);
    }
    if(flag)
    {
       sum+=p*d;
    }
}
void solve(){
    int n;cin>>n;
    memset(he,-1,sizeof he);
    for(int i=1;i<=n-1;++i)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1,0,1,1);
    cout<<fixed<<setprecision(15)<<sum;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

E. Useful Decomposition

题面

image-20240728164345868

输入

image-20240728164355977

输出

image-20240728164410270

思路

只能有一个分支点（branch>2），即为 yes，否则为 no，yes 的话就 dfs 找一下路径的末尾，标记一下，最后输出即可

当然，还有一个情况就是木有分支点，那就直接找到两端点，输出即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int he[N],ne[N],e[N],idx;
int st[N],branches[N],res[N],sum;
void add(int a,int b)
{
    ne[idx]=he[a];e[idx]=b;he[a]=idx++;
    branches[a]++;
}
void dfs(int u)
{
    st[u]=1;
    bool flag=false;
    for(int i=he[u];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])continue;
        flag=true;
        dfs(j);
    }
    if(!flag)res[u]=1,sum++;
}
void solve(){
    int n;cin>>n;
    memset(he,-1,sizeof he);
    for(int i=1;i<=n-1;++i)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    bool flag=false;
    int p=0;
    for(int i=1;i<=n;++i)
    {
        if(branches[i]>2)
        {
            if(!flag)flag=true,p=i;
            else
            {
                cout<<"No\n";
                return;
            }
        }
    }
    if(!p)
    {
        for(int i=1;i<=n;++i)
        {
            if(branches[i]==1)
            {
                p=i;
                break;
            }
        }
    }
    dfs(p);
    cout<<"Yes\n";
    cout<<sum<<'\n';
    for(int i=1;i<=n;++i)
    {
        if(res[i])cout<<p<<' '<<i<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

F. Cut 'em all!

题面

image-20240728165456522

输入

image-20240728165337309

输出

image-20240728165348077

思路

显然，n 为奇数时，不可能满足题意（切完后，点数都为偶数）必定是一偶一奇

n 为偶数时，必定能满足要求，因为可以不切即为 0，找最大切数即dfs 找子树的所有偶数/2，奇数就加到子树顶点上

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int he[N],ne[N],e[N],idx;
int st[N],res;
void add(int a,int b)
{
    ne[idx]=he[a];e[idx]=b;he[a]=idx++;
}
int dfs(int u)
{
    st[u]=1;
    int sum=1;
    for(int i=he[u];~i;i=ne[i])
    {
        int j=e[i];
        if(st[j])continue;
        int l=dfs(j);
        if(l%2==1)sum+=l;
        else res++;
    }
    return sum;
}
void solve(){
    int n;cin>>n;
    if(n%2==1)
    {
        cout<<-1<<'\n';
        return;
    }
    memset(he,-1,sizeof he);
    for(int i=1;i<=n-1;++i)
    {
        int a,b;cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs(1);
    cout<<res<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

G. Path Queries

题面

image-20240728170354063

输入

image-20240728170402659

输出

image-20240728170411462

思路

木有写出来，看了题解，先是 q 进行由小到大排序，因为小的满足的，大的只需要加点即可，再是对边按照 w 由小到大排序，然后就是不断联通（这里用的是并查集）在边的w小于等于q 的范围内联通，并求出这个 q 的对应答案，然后再进行下一个 q，即双循环解决

并查集部分还需要对 size 合并

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int n,m;
pair<int,int> q[N];
int p[N],sz[N];
int res[N],vis[N];
struct Node
{
	int a,b,c;
}edge[N];
void init(){
	for(int i=1;i<=n;++i)p[i]=i,sz[i]=1;
}
bool cmp(Node a,Node b)
{
	return a.c<b.c;
}
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
bool cmp2(pair<int,int>a,pair<int,int>b)
{
	return a.second<b.second;
}
int cal(int x)
{
	return (x-1)*x/2;
}
void solve(){
    cin>>n>>m;
    init();
    for(int i=1;i<=n-1;++i)
    {
    	int a,b,c;cin>>a>>b>>c;
    	if(a>b)swap(a,b);
    	edge[i]={a,b,c};
    }
    for(int i=1;i<=m;++i)
    {
    		cin>>q[i].first;
    		q[i].second=i;
    }
    sort(q+1,q+m+1);	
	sort(edge+1,edge+n,cmp);
	int cnt=1;
	int num=1;
	int ans=0;
	while(cnt<=m)
	{
		while(num<n&&edge[num].c<=q[cnt].first)
		{
			auto[a,b,c]=edge[num];
			ans-=cal(sz[find(a)]);ans-=cal(sz[find(b)]);
			if(find(b)!=find(a))
				sz[find(a)]+=sz[find(b)],sz[find(b)]=0;
			ans+=cal(sz[find(a)]);
			p[find(b)]=find(a);
			num++;
		}
		res[q[cnt].second]=ans;
		cnt++;
	}
	for(int i=1;i<=m;++i)cout<<res[i]<<' ';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;//cin>>T;
    while(T--)
    {
        solve();
    }
}

标签：idx,第一周,int,dfs,st,++,暑假,集训,he
From： https://www.cnblogs.com/violetoast/p/18328476

相关文章

  • ssy暑假集训暴力算法学习笔记
    7.28集训第六天今天t大学的学长peop1e来给我们讲课啦！人好帅呀嘿嘿嘿....内容如下模拟退火：定义模拟退火可以分成两个部分，一个是"模拟"，一个是"退火"，先介绍什么叫退火，贴一张百度百科的图吧：\(\\\)那这"退火"的定义有啥用吗？模拟退火就是用来模拟整个退火的过程(其实没啥相似......
  • 暑假集训SCP提高模拟10
    我（看着百度百科）：我已经知道这场谁组的题了CTH:谁我：你想想，能在模拟赛里塞四道数学题还玩邦的，还能有谁CTH:我不知道我：我不知道CTH:我知道了我：我知道了我：我是BobB.速度型高松灯很容易发现一种暴力思路：每次都将答案乘以对应的位数，然后直接把要加的数加进去，暴力模一下，不......
  • 暑假集训CSP提高模拟10
    暑假集训CSP提高模拟10组题人：@worldvanquisher\(T1\)P170.黑暗型高松灯\(0pts\)原题：CF1025GCompanyAcquisitions科技题目，直接贺官方题解了。考虑势能函数。如果我们使得每操作一步期望势能\(-1\)，那么初势能减末势能就是答案。设一个点有\(x\)个儿子的势能为\(f......
  • 2024暑假总结2
    7.22——数据结构上课+做题首先讲的是树剖。树剖核心就是根据树的一些特征（如深度、最大子树），将一棵树拆分成\(\log{n}\)个连续的树链，使得树上问题转化为线性问题，最后再用数据结构维护区间或是直接dp之类。由于我之前就比较熟悉树剖、还写过一些题，所以听得非常轻松，但是水平还......
  • 24-暑假软件工程周报（4）
    学习HBase与Hadoop生态系统的集成，并探索了如何利用Hadoop的各项功能来增强HBase的能力。1.如何通过MapReduce将数据从HDFS导入HBase。为了实现这一目标，我编写了一个简单的MapReduce作业。在Mapper中，我读取HDFS上的数据并转换为HBase支持的格式，在Reducer中，我将这些数据写入HBase表......
  • 暑假java自学进度总结03
    一.今日所学：1.标识符命名规则：必须：1>由数字，字母，下划线，美元符组成；2>不能以数字开头；3>不能是关键字；4>区分大小写；建议：1>命名方法，变量时用小驼峰命名法：*1.标识符是一个单词时，全部小写*2.标识符是多个单词组合时，第一个单词小写，其余单词首字母大写2>命名类名时用大驼峰命名法：......
  • 暑假模拟7
    暑假模拟7Permutations&Primes比较简单的构造题，容易发现所选区间只有包含1才可能产生贡献，此时考虑将2，3放在两边，1放在中间，其他数字不重要。构造方法正确性显然。注意\(n=1,2\)的情况。树上游戏Description这一天，\(Delov\)在和他的\(npy\)们在树上做游戏，他的\(npy\)们......
  • 暑假集训CSP提高模拟9
    又是挂分严重的一场T1大众点评T1交互题,注意边界处理,还有他的\(compare\)函数返回的是\(1,-1\),我以为是\(1,0\),爆零了还有特判\(N=1\)的情况点击查看代码//#include"ramen.h"////voidRamen(intN){//if(Compare(0,1)==1){//Answer(1,0);//}else{......
  • 暑假集训PVZ提高模拟9
    没关exe让这货挂了一天A.大众点评交互红题啊，交互会写，但是忘记判\(n=1\)了......
  • 暑假集训存录
    暑假集训存录推歌——BlackPink《뚜두뚜두》착한얼굴에그렇지못한태도 善良的脸蛋不屑的态度가녀린몸매속가려진volume은두배로 纤细的身体里隐藏着两倍的音量거침없이직진굳이보진않지눈치 势不可挡一直向前不必察言观色Black하면Pink우린......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99