本蒟蒻又卡题了！！

[阚宇阳1 (阚宇阳)]

努力理解

[阚宇阳1 (阚宇阳)]

我身为初二语文没上过90的天才，理解能力不太好

[Syxqwq (Loser_Syx)]

哦，节点i写成了节点u，然后答案的话得从深度小到大算（因为是 1 开始的）

[阚宇阳1 (阚宇阳)]

嗯，有V或q吗

[Syxqwq (Loser_Syx)]

QQ3377268867

[金杭东]

你们讨论去吧
到时候解决方案一人一半

[阚宇阳1 (阚宇阳)]

怎么一人一半

[Syxqwq (Loser_Syx)]

不要出现金钱相关讨论。

[金杭东]

不用
你可以解决方案给他
给我点赞就行

[阚宇阳1 (阚宇阳)]

嗯.

[Syxqwq (Loser_Syx)]

其实这题数据 n=100 直接算深度就可以，这个换根dp作为拓展解法罢。

[阚宇阳1 (阚宇阳)]

o，我试试

[Syxqwq (Loser_Syx)]

不会就别说话

[阚宇阳1 (阚宇阳)]

@尹思源

void dfs(vector<vector<int>>& graph, vector<bool>& visited, vector<int>& maxReach, int node) {
    visited[node] = true;
    for (int nei : graph[node]) {
        if (!visited[nei]) {
            dfs(graph, visited, maxReach, nei);
        }
        maxReach[node] = max(maxReach[node], maxReach[nei]);
    }
}
//代码 1 函数
void bfs(vector<vector<int>>& graph, vector<int>& maxReach, int start) {
    queue<int> q;
    q.push(start);
    maxReach[start] = start;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int nei : graph[node]) {
            if (maxReach[nei] < maxReach[node]) {
                maxReach[nei] = maxReach[node];
                q.push(nei);
            }
        }
    }
}
// 代码2 函数
    
    vector<vector<int>> graph(n);
    vector<bool> visited(n, false);
    vector<int> maxReach(n, -1);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
    }
    
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, visited, maxReach, i);
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (maxReach[i] == -1) {
            bfs(graph, maxReach, i);
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << maxReach[i] << " ";
    }
代码3 主函数

说方yc和贾zz的天才

[金杭东]

void bfs(int x)
{
	queue<node>q;
	q.push({x,0});
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		for(int i=0;i<p[now.x].size();++i)
		if(!vis[p[now.x][i]])
		{
			vis[p[now.x][i]]=1;
			s+=(now.ans+1)*a[p[now.x][i]];//累加距离
			q.push({p[now.x][i],now.ans+1});
		}
	}
}

给你搜索部分代码
只需要把所有x试一遍求最小值就行

[阚宇阳1 (阚宇阳)]

我在努力

[阚宇阳1 (阚宇阳)]

#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;


const int N = 105;
vector<int> a[N];
int w[N];
int sum[N];
int tot;
int minn = INT_MAX;

void dfs(int u, int parent) {
	sum[u] = w[u]; 
	for (int v : a[u]) {
		if (v == parent) continue; 
		dfs(v, u);

		sum[u] += sum[v];
	}
}

void f(int u, int parent) {

	int r = tot - sum[u];

	int l = 0;
	for (int v : a[u]) {
		if (v != parent) {

			l += sum[v];
		}
	}

	minn = min(minn, l);

	for (int v : a[u]) {
		if (v != parent) {
			f(v, u);
		}
	}
}

int main() {
	int n;
	cin >> n; 
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		tot += w[i]; 
	}

	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}

	dfs(1, -1);

	f(1, -1);

	cout << minn << endl;

	return 0;
}
努力了

[阚宇阳1 (阚宇阳)]

至少有10分

[Syxqwq (Loser_Syx)]

我帮你改一下。

[阚宇阳1 (阚宇阳)]

谢啦