\(\mathcal{Description}\)

给定一棵 \(n\) 个点的无根树，点有点权，每次选择两个不同的叶子，使它们间的简单路径的所有点权 \(-1\)，问能否将所有点权变成 \(0\)。

\(n\le10^5\)。

\(\mathcal{Solution}\)

这不就是我那道题的削弱版么 www。

考虑叶子 \(u\)，显然有 \(val_u\) 条路径经过 \(u\)。DFS 回溯时考虑合并儿子们的路径。假设儿子们向上的路径共 \(s\) 条，单个儿子向上路径最多有 \(m\) 条；我们拿 \(a\) 对路径在当前结点 \(u\) 处匹配成完整路径，剩下 \(b\) 条继续向上，那么有：

\[\begin{cases}
a+b=val_u\\
2a+b=s\\
a\le\min\{\lfloor\frac{s}2\rfloor,s-m\}
\end{cases}
\]

解出 \(a,b\)，判断是否合法即可。

\(\mathcal{Code}\)

#include <cstdio>

#include <cstdlib>

#include <iostream>

typedef long long LL;

const int MAXN = 1e5;

int n, ecnt, val[MAXN + 5], head[MAXN + 5], d[MAXN + 5];

struct Edge { int to, nxt; } graph[MAXN * 2 + 5];

inline void link ( const int s, const int t ) {

	graph[++ ecnt] = { t, head[s] };

	head[s] = ecnt;

}

inline int DFS ( const int u, const int f ) {

	if ( d[u] == 1 ) return val[u];

	LL sum = 0; int mx = 0;

	for ( int i = head[u], v; i; i = graph[i].nxt ) {

		if ( ( v = graph[i].to ) ^ f ) {

			int up = DFS ( v, u );

			sum += up, mx = std::max ( mx, up );

		}

	}

	if ( sum - val[u] > std::min ( sum >> 1, sum - mx )

		|| 2 * val[u] < sum || sum < val[u] ) puts ( "NO" ), exit ( 0 );

	return 2 * val[u] - sum;

	// a+b=val, 2a+b=sum, a<=min{sum/2,sum-mx}

}

int main () {

	scanf ( "%d", &n );

	for ( int i = 1; i <= n; ++ i ) scanf ( "%d", &val[i] );

	for ( int i = 1, u, v; i < n; ++ i ) {

		scanf ( "%d %d", &u, &v ), ++ d[u], ++ d[v];

		link ( u, v ), link ( v, u );

	}

	if ( n == 2 ) return puts ( val[1] == val[2] ? "YES" : "NO" ), 0;

	for ( int i = 1; i <= n; ++ i ) if ( d[i] > 1 ) return puts ( DFS ( i, 0 ) ? "NO" : "YES" ), 0;

	return 0;

}

巴特西

Solution -「AGC 010C」「AT 2304」Cleaning

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章