图论基础题
Pairs 判断边是否完全覆盖
1500分
Toad Ivan has 𝑚 pairs of integers, each integer is between 1 and 𝑛, inclusive. The pairs are (𝑎1,𝑏1),(𝑎2,𝑏2),…,(𝑎𝑚,𝑏𝑚).
He asks you to check if there exist two integers 𝑥 and 𝑦 (1≤𝑥<𝑦≤𝑛) such that in each given pair at least one integer is equal to 𝑥 or 𝑦.
Input
The first line contains two space-separated integers 𝑛 and 𝑚 (2≤𝑛≤300000, 1≤𝑚≤300000) — the upper bound on the values of integers in the pairs, and the number of given pairs.
The next 𝑚 lines contain two integers each, the 𝑖-th of them contains two space-separated integers 𝑎𝑖 and 𝑏𝑖 (1≤𝑎𝑖,𝑏𝑖≤𝑛,𝑎𝑖≠𝑏𝑖) — the integers in the 𝑖-th pair.
Output
Output "YES" if there exist two integers 𝑥 and 𝑦 (1≤𝑥<𝑦≤𝑛) such that in each given pair at least one integer is equal to 𝑥 or 𝑦. Otherwise, print "NO". You can print each letter in any case (upper or lower).
4 6 1 2 1 3 1 4 2 3 2 4 3 4
NO
5 4 1 2 2 3 3 4 4 5
YES
题目大意
给M个点对，让选一个x和y，让每一个点对要么有x，要么有y。问是否可行？
方法
把每一个点对想象成一条边，最开始选则一条边，其中两个点A，B，要么A令其为X，要么是B是X，把X相关联的边都标记成1，
然后选一条标记是0的边，两个端点C，D，要么C为Y，要么D为Y。然后就看X和Y能不能覆盖所有的边了。一共就4个情况，枚举一下，然后判断其合法性即可。
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int N,M;
struct Edg
{
int x,y;
}edg[maxn];
int h[maxn],e[maxn],ne[maxn],idx = 1;
bool vis[maxn];
void add(int a,int b){
e[++idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
bool judge(int x){
memset(vis,0,sizeof vis);
int cnt1 = 0,cnt2 = 0,cnt3 = 0;
for(int i = h[x];i;i = ne[i]){
vis[i] = 1;
vis[i^1] = 1;
cnt1++;
}
int nx = -1,ny = -1;
for(int u = 1;u<=N;u++){
for(int i = h[u];i;i = ne[i]){
if(vis[i]) continue;
else{
nx = u,ny = e[i];
break;
}
}
}
if(nx == -1) return 1;
for(int i = h[nx];i;i = ne[i]){
if(!vis[i]) cnt2++;
}
for(int i = h[ny];i;i = ne[i]){
if(!vis[i]) cnt3++;
}
if(cnt1 + cnt2 == M || cnt1 + cnt3 == M) return 1;
return 0;
}
int main(){
// debug_in;
read(N,M);
for(int i = 1;i<=M;i++){
read(edg[i].x,edg[i].y);
add(edg[i].x,edg[i].y);
add(edg[i].y,edg[i].x);
}
bool ok = 0;
ok = ok|judge(edg[1].x);
ok = ok|judge(edg[1].y);
if(ok) puts("YES");
else puts("NO");
return 0;
} Edgy Trees并查集
1500分
You are given a tree (a connected undirected graph without cycles) of 𝑛 vertices. Each of the 𝑛−1 edges of the tree is colored in either black or red.
You are also given an integer 𝑘. Consider sequences of 𝑘 vertices. Let's call a sequence [𝑎1,𝑎2,…,𝑎𝑘] good if it satisfies the following criterion:
We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from 𝑎1 and ending at 𝑎𝑘.
Start at 𝑎1, then go to 𝑎2 using the shortest path between 𝑎1 and 𝑎2, then go to 𝑎3 in a similar way, and so on, until you travel the shortest path between 𝑎𝑘−1 and 𝑎𝑘.
If you walked over at least one black edge during this process, then the sequence is good.
Consider the tree on the picture. If 𝑘=3 then the following sequences are good: [1,4,7], [5,5,3] and [2,3,7]. The following sequences are not good: [1,4,6], [5,5,5], [3,7,3].
There are 𝑛𝑘 sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo 109+7.
Input
The first line contains two integers 𝑛 and 𝑘 (2≤𝑛≤105, 2≤𝑘≤100), the size of the tree and the length of the vertex sequence.
Each of the next 𝑛−1 lines contains three integers 𝑢𝑖, 𝑣𝑖 and 𝑥𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛, 𝑥𝑖∈{0,1}), where 𝑢𝑖 and 𝑣𝑖 denote the endpoints of the corresponding edge and 𝑥𝑖 is the color of this edge (0 denotes red edge and 1 denotes black edge).
Output
Print the number of good sequences modulo 1e9+7.
4 4 1 2 1 2 3 1 3 4 1
252
题目大意：
给定N个点的树，里面的边要么是红色，要么是黑色，给定一个K，假如一个条路径有K个点，相邻两个点都是以最短路的方式走，如果路途中经过一条黑色的边，那么由这K个点组成的路径是good路径。问给定的树中，有多少个K个点能组成good路径？
方法
其实样例已经很清楚了。就是反着去想，用补集的思想去解。
答案 = 总路径数 - 不能经过黑色边的路径数
总路径数 =
不能经过黑色边的路径数 = sum of (一个不含黑色边的联通块的点个数)
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 0x3f3f3f3f;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
const int mod = 1000000007;
int N,K;
int fa[maxn],sz[maxn];
int find(int x){
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
ll ksm(ll a,ll b){
ll res = 1;
while(b){
if(b&1) res = res * a%mod;
a = a*a%mod;
b>>=1;
}
return res;
}
int main(){
// debug_in;
read(N,K);
for(int i = 1;i<=N;i++) fa[i] = i,sz[i] = 1;
for(int i = 1;i<=N-1;i++){
int x,y,t;read(x,y,t);
if(t == 0) {
int fx = find(x),fy = find(y);
fa[fx] = fy;
sz[fy] += sz[fx];
}
}
ll ans = ksm(N,K);
for(int i = 1;i<=N;i++){
if(find(i) == i){
ans = (ans - ksm(sz[i],K) + mod) %mod;
}
}
printf("%lld\n",ans);
return 0;
} Mortal Kombat Tower 最短路or dp
1500分
You and your friend are playing the game Mortal Kombat XI. You are trying to pass a challenge tower. There are 𝑛 bosses in this tower, numbered from 1 to 𝑛. The type of the 𝑖-th boss is 𝑎𝑖. If the 𝑖-th boss is easy then its type is 𝑎𝑖=0, otherwise this boss is hard and its type is 𝑎𝑖=1.
During one session, either you or your friend can kill one or two bosses (neither you nor your friend can skip the session, so the minimum number of bosses killed during one session is at least one). After your friend session, your session begins, then again your friend session begins, your session begins, and so on. The first session is your friend's session.
Your friend needs to get good because he can't actually kill hard bosses. To kill them, he uses skip points. One skip point can be used to kill one hard boss.
Your task is to find the minimum number of skip points your friend needs to use so you and your friend kill all 𝑛 bosses in the given order.
For example: suppose 𝑛=8, 𝑎=[1,0,1,1,0,1,1,1]. Then the best course of action is the following:
your friend kills two first bosses, using one skip point for the first boss;
you kill the third and the fourth bosses;
your friend kills the fifth boss;
you kill the sixth and the seventh bosses;
your friend kills the last boss, using one skip point, so the tower is completed using two skip points.
You have to answer 𝑡 independent test cases.
Input
The first line of the input contains one integer 𝑡 (1≤𝑡≤2⋅104) — the number of test cases. Then 𝑡 test cases follow.
The first line of the test case contains one integer 𝑛 (1≤𝑛≤2e5) — the number of bosses. The second line of the test case contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (0≤𝑎𝑖≤1), where 𝑎𝑖 is the type of the 𝑖-th boss.
It is guaranteed that the sum of 𝑛 does not exceed 2⋅105 (∑𝑛≤2e5).
Output
For each test case, print the answer: the minimum number of skip points your friend needs to use so you and your friend kill all 𝑛 bosses in the given order.
6 8 1 0 1 1 0 1 1 1 5 1 1 1 1 0 7 1 1 1 1 0 0 1 6 1 1 1 1 1 1 1 1 1 0
2 2 2 2 1 0
题目大意：
两个人轮流走，1号先走，然后再0号走，依次交替。每个人每一次要么走1步，要么走2步。1号走的代价是经过1的个数，2号走的代价都是0.问走完这N个点总代价最小是多少？
方法1：
最短路，建立图。每一个点i可以向i+1,i+2连1号走的代价边，也可以向0号走的代价边(代价为0)。然后在跑最短路的时候，必须上一次走的边和本次走的边是不同人走的，才可以走。然后答案就是最终N+1是1号到达的代价，跟N+1是0号到达的代价最小值。
dis数组，vis数组都要建立两份，分别是1号，和0号
方法2: :表示0/1号走到第i个位置的最优值，
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int T,N;
int h[maxn],e[maxn],w[maxn],tag[maxn],ne[maxn],idx = 1;
int a[maxn];
struct node
{
int u,w,tg;
bool operator <(const node &o) const{
return w > o.w;
}
};
priority_queue<node> q;
int dis[maxn][2];
bool vis[maxn][2];
void add(int a,int b,int c,int d){
e[++idx] = b;
w[idx] = c;
tag[idx] = d;
ne[idx] = h[a];
h[a] = idx;
}
void build(){
for(int i = 1;i<=N;i++){ //one
int cnt = a[i];
add(i,i+1,cnt,1);
add(i,i+1,0,0);
if(i+1<=N){
cnt += a[i+1];
add(i,i+2,cnt,1);
add(i,i+2,0,0);
}
}
}
void solve(){
for(int i = 1;i<=N+1;i++) {
dis[i][0] = dis[i][1] = inf;
vis[i][0] = vis[i][1] = 0;
}
q.push({1,0,0});
dis[1][0] = 0;
while(q.size()){
node cur = q.top();q.pop();
int u = cur.u,tgu = cur.tg;
if(vis[u][tgu]) continue;
vis[u][tgu] = 1;
for(int i = h[u];i;i = ne[i]){
int v = e[i];
int tgv = tag[i];
if(tgv == tgu) continue;
if(dis[u][tgu] + w[i] < dis[v][tgv]){
dis[v][tgv] = dis[u][tgu] + w[i];
q.push({v,dis[v][tgv],tgv});
}
}
}
printf("%d\n",min(dis[N+1][0],dis[N+1][1]));
}
int main(){
// debug_in;
read(T);
while(T--){
idx = 1;
read(N);
for(int i = 1;i<=N;i++) h[i] = 0;
for(int i = 1;i<=N;i++) read(a[i]);
build();
solve();
}
return 0;
} #include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int T,N;
int a[maxn];
int dp[maxn][2];
void solve(){
for(int i = 1;i<=N+1;i++) dp[i][0] = dp[i][1] = inf;
dp[1][0] = 0;
for(int i = 1;i<=N+1;i++){
for(int tg = 0;tg<=1;tg++){
if(i-1>=1) {
int w = tg == 1? a[i-1]:0;
dp[i][tg] = min(dp[i-1][tg^1] + w,dp[i][tg]);
}
if(i-2>=1) {
int w = tg == 1? a[i-1] + a[i-2]:0;
dp[i][tg] = min(dp[i-2][tg^1] + w,dp[i][tg]);
}
}
}
printf("%d\n",min(dp[N+1][0],dp[N+1][1]));
}
int main(){
// debug_in;
read(T);
while(T--){
read(N);
for(int i = 1;i<=N;i++) read(a[i]);
solve();
}
return 0;
} Cut 'em all! 略微树形dp
1400分
You're given a tree with 𝑛 vertices.
Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.
Input
The first line contains an integer 𝑛 (1≤𝑛≤105) denoting the size of the tree.
The next 𝑛−1 lines contain two integers 𝑢, 𝑣 (1≤𝑢,𝑣≤𝑛) each, describing the vertices connected by the 𝑖-th edge.
It's guaranteed that the given edges form a tree.
Output
Output a single integer 𝑘 — the maximum number of edges that can be removed to leave all connected components with even size, or −1 if it is impossible to remove edges in order to satisfy this property.
4 2 4 4 1 3 1
1
3 1 2 1 3
-1
10 7 1 8 4 8 10 4 7 6 5 9 3 3 5 2 10 2 5
4
2 1 2
0
题目大意：
给你一棵树，让你尽可能删除多的边，使得剩下的联通快都含有偶数个点，最多删除多少边？
方法
对于一个父节点，如果它的一颗子树合法删边后跟父节点连接的点数为cnt[j]，对于cnt[j]只可能是奇数，因为如果是偶数，那么就可以直接断开与父节点相连接的边，而自身也是偶数点的联通块。
父节点的不同子树cnt[j] 只能依靠父节点为桥梁，让其位于偶数点的联通块中。所以所有的子树cnt[j]都加在父节点上，如果以此时父节点cnt[i]是偶数那么就可以断开父节点与它的父节点的边了。
如果向上传递到根节点后，cnt[i] %2 == 1，那么答案为-1
否则答案减去1，因为根节点没有父节点，多算了一次
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int N;
int h[maxn],e[maxn],ne[maxn],idx = 1;
int dp[maxn];
int ans = 0;
void add(int a ,int b){
e[++idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
int dfs(int u,int fa = -1){
int cnt = 1;
for(int i = h[u];i;i = ne[i]){
int v = e[i];
if(v == fa) continue;
cnt += dfs(v,u);
}
if(cnt%2 == 0) {
ans++;
return 0;
}else return 1;
}
int main(){
// debug_in;
read(N);
for(int i = 1;i<=N-1;i++){
int u,v;read(u,v);
add(u,v);
add(v,u);
}
int cnt = dfs(1);
if(cnt%2 == 1) puts("-1");
else printf("%d\n",ans-1);
return 0;
} Lunar New Year and a Wander优先队列
1500分
Lunar New Year is approaching, and Bob decides to take a wander in a nearby park.
The park can be represented as a connected graph with 𝑛 nodes and 𝑚 bidirectional edges. Initially Bob is at the node 1 and he records 1 on his notebook. He can wander from one node to another through those bidirectional edges. Whenever he visits a node not recorded on his notebook, he records it. After he visits all nodes at least once, he stops wandering, thus finally a permutation of nodes 𝑎1,𝑎2,…,𝑎𝑛 is recorded.
Wandering is a boring thing, but solving problems is fascinating. Bob wants to know the lexicographically smallest sequence of nodes he can record while wandering. Bob thinks this problem is trivial, and he wants you to solve it.
A sequence 𝑥 is lexicographically smaller than a sequence 𝑦 if and only if one of the following holds:
𝑥 is a prefix of 𝑦, but 𝑥≠𝑦 (this is impossible in this problem as all considered sequences have the same length);
in the first position where 𝑥 and 𝑦 differ, the sequence 𝑥 has a smaller element than the corresponding element in 𝑦.
Input
The first line contains two positive integers 𝑛 and 𝑚 (1≤𝑛,𝑚≤105), denoting the number of nodes and edges, respectively.
The following 𝑚 lines describe the bidirectional edges in the graph. The 𝑖-th of these lines contains two integers 𝑢𝑖 and 𝑣𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛), representing the nodes the 𝑖-th edge connects.
Note that the graph can have multiple edges connecting the same two nodes and self-loops. It is guaranteed that the graph is connected.
Output
Output a line containing the lexicographically smallest sequence 𝑎1,𝑎2,…,𝑎𝑛 Bob can record.
Examples
input
3 2 1 2 1 3
output
1 2 3
input
5 5 1 4 3 4 5 4 3 2 1 5
output
1 4 3 2 5
input
10 10 1 4 6 8 2 5 3 7 9 4 5 6 3 4 8 10 8 9 1 10
output
1 4 3 7 9 8 6 5 2 10
题目大意
对于一个图，要以字典序最小遍历所有的节点，每个节点至少被经过一次。输出方案
方法
维护一个优先队列，从u走到v，那么v就可以走到u能走到的所有节点了，那么把u的所有没有遍历的节点放入到优先队列中。供v下一步走哪做选择。v到了x，那么x就能走v能到达的所有节点，然后又把v的所有没有遍历的节点放入到优先队列中，重复这个过程。
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int N,M;
vector<int> adj[maxn];
bool vis[maxn];
int ans[maxn],tail;
priority_queue<int,vector<int>,greater<int> > q;
bool in_q[maxn];
void solve(){
q.push(1);in_q[1] = 1;
while(q.size()){
int u = q.top();q.pop();in_q[u] = 0;
ans[++tail] = u;
vis[u] = 1;
for(auto v:adj[u]){
if(vis[v] || in_q[v]) continue;
q.push(v);in_q[v] = 1;
}
adj[u].clear();
}
int sp = 1;
for(int i = 1;i<=tail;i++) {
if(sp) sp = 0;else putchar(' ');
printf("%d",ans[i]);
}
}
int main(){
// debug_in;
read(N,M);
for(int i = 1;i<=M;i++){
int x,y;read(x,y);
adj[x].pb(y);
adj[y].pb(x);
}
solve();
return 0;
} Peculiar apple-tree树 + 思维
1500分
In Arcady's garden there grows a peculiar apple-tree that fruits one time per year. Its peculiarity can be explained in following way: there are n inflorescences, numbered from 1 to n. Inflorescence number 1 is situated near base of tree and any other inflorescence with number i (i > 1) is situated at the top of branch, which bottom is pi-th inflorescence and pi < i.
Once tree starts fruiting, there appears exactly one apple in each inflorescence. The same moment as apples appear, they start to roll down along branches to the very base of tree. Each second all apples, except ones in first inflorescence simultaneously roll down one branch closer to tree base, e.g. apple in a-th inflorescence gets to pa-th inflorescence. Apples that end up in first inflorescence are gathered by Arcady in exactly the same moment. Second peculiarity of this tree is that once two apples are in same inflorescence they annihilate. This happens with each pair of apples, e.g. if there are 5 apples in same inflorescence in same time, only one will not be annihilated and if there are 8 apples, all apples will be annihilated. Thus, there can be no more than one apple in each inflorescence in each moment of time.
Help Arcady with counting number of apples he will be able to collect from first inflorescence during one harvest.
Input
First line of input contains single integer number n (2 ≤ n ≤ 100 000) — number of inflorescences.
Second line of input contains sequence of n - 1 integer numbers p2, p3, ..., pn (1 ≤ pi < i), where pi is number of inflorescence into which the apple from i-th inflorescence rolls down.
Output
Single line of output should contain one integer number: amount of apples that Arcady will be able to collect from first inflorescence during one harvest.
Examples
input
3 1 1
output
1
input
5 1 2 2 2
output
3
input
18 1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4
output
4
Note
In first example Arcady will be able to collect only one apple, initially situated in 1st inflorescence. In next second apples from 2nd and 3rd inflorescences will roll down and annihilate, and Arcady won't be able to collect them.
In the second example Arcady will be able to collect 3 apples. First one is one initially situated in first inflorescence. In a second apple from 2nd inflorescence will roll down to 1st (Arcady will collect it) and apples from 3rd, 4th, 5th inflorescences will roll down to 2nd. Two of them will annihilate and one not annihilated will roll down from 2-nd inflorescence to 1st one in the next second and Arcady will collect it.
题目大意
有一颗树，每一个节点有一个苹果，有一个人只能在根节点接苹果。每一秒每个苹果都会走到其父节点处，如果有两个苹果同时走到父节点，那么这两个苹果就会坏掉。也就是奇数留一个不坏，偶数都坏掉。
方法
考虑某一层的苹果数，无论这层苹果有多少个，最多只会保留一个苹果。对于苹果是偶数个的减少，所以如果这一层是奇数个苹果，那么必定会有一个留下来。所以就是判断某一层苹果的奇偶性，是奇数就加1，偶数加0。
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;
template<class T>void read(T &x){
T s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
read(h);
read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}
template <class T>
T unpacker(const T& t){
cout<<' '<<t;
return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
cout << t;
DummyWrapper(unpacker(data)...);
cout << '\n';
}
//--------------------------------------------
int N;
int h[maxn],e[maxn],ne[maxn],idx = 1;
int cnt[maxn];
void add(int a,int b){
e[++idx] = b;
ne[idx] = h[a];
h[a] = idx;
}
void dfs(int u,int lev){
cnt[lev]++;
for(int i = h[u];i;i = ne[i]){
int v = e[i];
dfs(v,lev+1);
}
}
int main(){
// debug_in;
read(N);
for(int i = 2;i<=N;i++){
int f;read(f);
add(f,i);
}
dfs(1,1);
int ans = 0;
for(int i = 1;i<=N;i++){
if(cnt[i]%2) ans++;
}
printf("%d\n",ans);
return 0;
} 
没问题