深搜更新节点。。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=320000;
int Adj[maxn],Size,n,repair[maxn];
bool vis[maxn],rep[maxn];
typedef struct node
{
int to,next,rp;
}Edge;
Edge E[maxn];
void init()
{
Size=0;
memset(Adj,-1,sizeof(Adj));
}
void Add_Edge(int u,int v,int r)
{
E[Size].to=v; E[Size].rp=r;
E[Size].next=Adj[u];
Adj[u]=Size++;
}
void dfs(int x)
{
vis[x]=true;
for(int j=Adj[x];~j;j=E[j].next)
{
int TO=E[j].to;
if(vis[TO]) continue;
if(E[j].rp==1)///不要修路
{
repair[TO]=repair[x];
dfs(TO);
}
else if(E[j].rp==2)///要修路
{
rep[TO]=true;
rep[repair[x]]=false;
repair[TO]=TO;
dfs(TO);
}
}
}
int main()
{
cin>>n;
init();
for(int i=0;i<n-1;i++)
{
int a,b,c;
cin>>a>>b>>c;
Add_Edge(a,b,c);
Add_Edge(b,a,c);
}
dfs(1);
int ans=0;
for(int i=1;i<=n;i++) if(rep[i]) ans++;
cout<<ans<<endl;
for(int i=1;i<=n;i++) if(rep[i]) cout<<i<<" ";
return 0;
}
分享到:
相关推荐
Codeforces Round #632 (Div. 2) C. Eugene and an array 题意: 求出一个数列中子区间满足 此区间的任意子区间之和 不为0的区间个数。 思路: 考虑用dp[x]dp[x]dp[x]记录前缀和为xxx的区间右端点。 那么这道题其实...
Codeforces round 678 D2_Codeforces_源码
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
Codeforces部门2,A # And a2oj Ladder 4 some problems Ladder URL:http://a2oj.com/Ladder.jsp?ID=4难度等级:2问题提示: 1- 4A. Watermelon: http://codeforces.com/problemset/problem/4/A 2- 71A. Way Too ...
题意: 在集合 S=1,2,⋯,nS={1,2,⋯,n}S=1,2,⋯,n 中,对于每个正整数 kkk ,找出一个大小为 kkk 的子集,使得该子集中两两间最大公因数的最大值最小,求这个最小值。 我们考虑如何构造两两间最大公因数的最大值最小...
题意: 给出 nnn 个点,n−1n-1n−1 条边,最多询问 n2\frac{n}{2}2n 次,每次询问 u,vu,vu,v,会给出 uvuvuv的最近公共祖先,求树的根。 ...操作就是一个删除叶子节点的过程。 AC代码: const int N = 1010;...
如果a嘲讽b,b嘲讽c,那么(a,b,c)是一个三元组 问每次操作之后一共有多少对三元组 数据范围:n,m<=1e5,q<=1e5 三元组图例(未修改工资时): 图中三元组一共4组: 4->3->1 4->3->2 4->2->1 3->2->1 解法...
codeforces每日一练。 题意: 给定n个点,m条有向边,以及k时间。求不超过k时间1-n最多能经过多少个点。 思路: 数据<=5000,说明是个暴力dp。 那么可以用dp[i][j]维护从1到i点经过了j个点,然后初始化为inf,再设...
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
Educational Codeforces Round 157D. XOR Construction
一个简单的基于ASP.net的个人聊天室网页。
E. Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an....Choose a pair of two neighboring equal ...
codeforces每日一练。 题意: 有n张卡片,卡片上的数字就是分数,比如说甲乙两人抽卡,三局两胜,一局得分高的胜,求在甲赢了两局的情况下乙赢了第三局且总分比甲高的概率。 思路: 数据1e3,很明显的On^2算法,所以...
codeforces.dev codeforces.dev 这是应用程序的项目模板。 它位于 。 要使用基于此模板创建一个新项目: npx degit sveltejs/template svelte-app cd svelte-app 请注意,您将需要安装 开始吧 安装依赖项... ...
F. Maximum White Subtree time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given a tree consisting of n vertices. A tree is a connected ...
D. Ehab the Xorcist ...Given 2 integers u and v, find the shortest array such that bitwise-xor of its elements is u, and the sum of its elements is v. Input The only line contains 2 integers u and v
Codeforces Guide.zip
Codeforces 1105B - Zuhair and Strings 测试点37个(全)