第四天作业

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
struct node{
	int l,r;
}a[1001000];//记录每个节点的左右节点
int Max=-1,n;
void dfs(int root,int step){
	if(root==0) return;//如果该节点为0（即上它的爸爸没有这个儿子），返回
	Max=max(Max,step);//记录最大值
	dfs(a[root].l,step+1);//搜索它的左儿子
	dfs(a[root].r,step+1);//搜索它的右儿子
}
int main(){
	cin>>n;//输入n
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;//输入该节点的左节点和右节点
	}
	dfs(1,1);//从1号节点，深度为1开始搜索 
	cout<<Max;//输出最大值
	return 0;
}

#include <iostream>
#include <vector>
using namespace std;
void dfs(int node, vector<vector<int>>& children, vector<int>& subtree_size) {
    for (int child : children[node]) {
        dfs(child, children, subtree_size);
        subtree_size[node] += subtree_size[child];
    }
}
int main() {
    int n;
    cin >> n;
    vector<vector<int>> children(n + 1);
    for (int i = 2; i <= n; ++i) {
        int parent;
        cin >> parent;
        children[parent].push_back(i);
    }
    vector<int> subtree_size(n + 1, 1);
    dfs(1, children, subtree_size);
    for (int i = 1; i <= n; ++i) {
        cout << subtree_size[i] << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
vector<int> c[maxn];
int weight[maxn];
int sum[maxn];
int n;
void dfs(int node) {
    sum[node] = weight[node];
    for(int i=0; i<c[node].size(); i++) {
        int child = c[node][i];
        dfs(child);
        sum[node] += sum[child];
    }
}
int main() {
    cin >> n;
    for(int i=1; i<=n; i++) {
        int f, w;
        cin >> f >> w;
        weight[i] = w;
        if(f != 0) {
            c[f].push_back(i);
        }
    }
    dfs(1);
    for(int i=1; i<=n; i++) {
        cout << sum[i] << endl;
    }
    return 0;
}

#include<iostream>
#define ll long long
using namespace std;
void dfs(ll i,ll x,ll n){
	if(x == 1){
		return;
	}
	if(i*i>n){
		if(x>1){
			cout<<x;
		}
		return ;
	}
	while(x%i==0){
		x/=i;
		cout<<i;
	}
	dfs(i+1,x,n);
}
int main(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		dfs(2,n,n);
		cout<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
vector <int> g[123456];
bool vis[123456];
int ans,n,d;
void dfs(int now,int dis)
{
	vis[now]=1;
	if(dis==d) return;
	for(int i=0;i<g[now].size();i++)
	{
		if(!vis[g[now][i]])
		{
			dfs(g[now][i],dis+1);
			ans++;
		}
	}
}
int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1,0);
	cout<<ans;
	return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0][0] = true;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        if (x == n - 1 && y == m - 1) {
            cout << "Yes" << endl;
            return 0;
        }
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] == '.' && !visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

#include<iostream>
using namespace std;

int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
char grid[105][105];

void dfs(int x, int y) {
    grid[x][y] = '.';
    for (int i = 0; i < 8; i++) {
        int xa = x + dx[i];
        int ya = y + dy[i];
        if (xa >= 1 && xa <= n && ya >= 1 && ya <= m && grid[xa][ya] == 'W') {
            dfs(xa, ya);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (grid[i][j] == 'W') {
                ans++;
                dfs(i, j);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

#include<iostream>
using namespace std;
int n,m,t,sx,sy,fx,fy,vis[1000][1000],ans;
int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
void dfs(int x,int y){
	if(x==fx&&y==fy){
		ans++;
		return;
	}
	for(int i=0;i<4;i++){
		int xa=x+dx[i],ya=y+dy[i];
		if(vis[xa][ya]==0&&xa<=n&&xa>0&&ya<=m&&ya>0){
			vis[xa][ya]=1;
			dfs(xa,ya);
			vis[xa][ya]=0;
		}
	}
}
int main(){
	cin>>n>>m>>t>>sx>>sy>>fx>>fy;
	for(int i=0,x,y;i<t;i++){
		cin>>x>>y;
		vis[x][y]=1;
	}
	vis[sx][sy]=1;
	dfs(sx,sy);
	cout<<ans;
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
void dfs(int n, int k, vector<int>& path, vector<bool>& used) {
    if (path.size() == k) {
        for (int num : path) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }   
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            used[i] = true;
            path.push_back(i);
            dfs(n, k, path, used);
            path.pop_back();
            used[i] = false;
        }
    }
}
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> path;
    vector<bool> used(n + 1, false);
    dfs(n, k, path, used);
    return 0;
}

#include <iostream>
using namespace std;

int n, m;
int arr[25]; // 存储当前组合

void dfs(int start, int depth) {
    // 如果已经选择了m个数，输出当前组合
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << arr[i];
            if (i < m - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    // 从start到n枚举下一个数
    for (int i = start; i <= n; i++) {
        arr[depth] = i; // 选择当前数
        dfs(i + 1, depth + 1); // 递归选择下一个数
    }
}

int main() {
    cin >> n >> m; // 输入n和m
    dfs(1, 0); // 从1开始深度优先搜索
    return 0;
}