当前位置:网站首页>codeforces Valera and Elections (这思维题是做不明白了)
codeforces Valera and Elections (这思维题是做不明白了)
2022-08-09 06:36:00 【先求一个导】
题目
题意: 给定一棵以1为根的树,有的边坏了。选择尽量少的点,这些点可以修复其到1的路径上坏的边。
思路: dfs。如果某个叶子对应的边恰好是坏的,那必定修复。之后我想的是从这里回溯到点1,把对应的边修好。但是时间复杂度高而且比较难实现。所以可以拿一个变量维护某个点对应的子树中是否存在点被选择过,这样即使他头上的边是坏的,也不会额外计数,而某个点对应子树中没有点被选过,他也是必选的。这种带返回值的dfs写的比较少,着实菜。
时间复杂度: O(n)
代码:
// Problem: C. Valera and Elections
// Contest: Codeforces - Codeforces Round #216 (Div. 2)
// URL: https://codeforces.com/problemset/problem/369/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,k,T;
struct node{
int v,op;
bool operator<(const node&rhs)
{
return op > rhs.op;
}
};
vector<node> va[N];
int ans;
vector<int> res;
int dfs(int cur,int fa,int last) //上一条边
{
bool t = 0; //是否有节点被选
bool leaf = 1;
for(auto tmp:va[cur])
{
int j = tmp.v;
if(j==fa) continue; leaf = 0;
int op = tmp.op;
t |= dfs(j,cur,op);
}
// cout<<cur<<" "<<fa<<":"<<t<<endl;
if(leaf&&last==2)
{
res.push_back(cur); return true;}
if(!t && last==2) {
res.push_back(cur); t = true;} //没有孩子选
return t;
}
void solve()
{
cin>>n;
for(int i=0;i<n-1;++i)
{
int x,y,op; cin>>x>>y>>op;
va[x].push_back({
y,op}),va[y].push_back({
x,op});
}
// for(int i=1;i<=n;++i) sort(va[i].begin(),va[i].end());
dfs(1,0,1);
cout<<res.size()<<"\n";
for(int i=0;i<res.size();++i)
{
if(i) cout<<" ";
cout<<res[i];
}
}
signed main(void)
{
solve();
return 0;
}
边栏推荐
- Introduction of convenient functions and convenient shortcut keys of vs tomato assistant
- db.sqlite3 has no "as Data Source" workaround
- Word文件的只读模式没有密码怎么退出?
- 变压器的工作原理(图解,原理图讲解,一看就懂)
- 报错jinja2.exceptions.UndefinedError: ‘form‘ is undefined
- leetcode 之盛水问题
- 2022.8.8DAY628
- [HNOI2002]营业额统计
- 集合内之部原理总结
- APP product source data interface (taobao, jingdong/spelling/suning/trill platform details a lot data analysis interface) code and docking tutorial
猜你喜欢
A test engineer with an annual salary of 35W was laid off. Personal experience: advice that you have to listen to
leetcode 之盛水问题
IQ Products巨细胞病毒CMV感染检测试剂盒的特征和应用
C# 利用iTextSharp画PDF
使用百度EasyDL实现智能垃圾箱
一道很简答但是没答对的SQL题
缓存技术使用
leetcode 之 70 爬楼梯问题 (斐波那契数)
中英文说明书丨TRC D-阿卓糖(D-Altrose)
How to find package information and pin definitions for NXP S32K1xx series microcontrollers
随机推荐
C# 利用iTextSharp画PDF
Fragments
Web APIs BOM- 操作浏览器:本地存储
idea中PlantUML插件使用
Go lang1.18入门精炼教程——第一章:环境搭建
[HNOI2002]营业额统计
Excel受保护的工作表怎么操作?
bzoj 5333 [Sdoi2018]荣誉称号
The singleton pattern
IQ Products CMV Brite Turbo试剂盒的原理
电学知识的疑问
MongDb的查询方式
报错:FSADeprecationWarning: SQLALCHEMY_TRACK_MODIFICATIONS重大开销和将disab补充道
ByteDance Written Exam 2020 (Douyin E-commerce)
Inception V3 闭眼检测
数据库中间件-jdbi
Redis 2 - 高级
Gao Zelong, a famous digital collection expert and founder of the Digital Collection Conference, was interviewed by China Entrepreneur Magazine
leetcode 之 零移位
Remember a nest.js route that matches all the path problems that follow