CF#660 C - Uncle Bogdan and Country Happiness
8420 ワード
标题:n都市(1は首都)、n-1道路が連なっています.m人の市民は良い気持ちと悪い気持ちを持っている.市民はそれぞれの都市に住んでいて、首都で働いていて、退勤して家に帰るときは気持ちが悪くなりますが、悪い気持ちはよくなく、都市の中では気持ちが変わりません.幸福指数f[x]は都市xを通るすべての人の中で良い気持ちの人数-悪い気持ちの人数である.
要求、幸福指数の測量器は正確に“YES”を出力することを測量して、さもなくば“NO”を出力します
入力:
最初の行には、整数T(1≦t≦10000)が含まれています.テスト例の数です.各試験例の第1行は、2つの整数nおよびm(1≦n≦105;0≦m≦109)--都市および市民の数を含む.各試験例の2行目はn整数p 1,p 2,...,を含む.pn(0≦pi≦m;p 1+p 2+…)+pn=MP 1+p 2+…+pn=m)のうち、pipiは第2都市に居住する人数である.3行目はnn個の整数h 1,h 2,....hh 1,h 2,...,HN(−109≦hi≦109−109≦hi≦109)は,hiがi番目の都市の計算幸福指数である.次にn−1行は、道路の説明を含み、各行に1本である.各線は、xiとyi(1≦xi,yi≦n;xi≠yi)の2つの整数を含み、xiとyiはi番目の道路で接続された都市である.すべての試験例からのnの和が2⋅105を超えないことを保証する.
サンプルを入力:
出力:
各試験例について、収集したデータが正しい場合は「YES」を印刷する.そうでなければ、「NO」の文字.
出力サンプル:
問題:
dfs
都市xに住む人はp[x]個,計測器指数はh[x]であり,この都市を通る総数はa[x]である.気持ちの良い人はgood[x]人がいて、気持ちの悪い人はbad[x]人がいます
したがって、a[x]=good[x]+bad[x],h[x]=good[x]-bad[x]
3つの制約があります.
1.a[x]+h[x]は2で割り切れる.
2.good[x]の区間範囲は[0,a[x]];
3.親ノード都市の気分が良い人は子ノード都市の気分が良い人より大きい(この都市を通ると気分が悪くなるかもしれないが、良くならない)
コード:
要求、幸福指数の測量器は正確に“YES”を出力することを測量して、さもなくば“NO”を出力します
入力:
最初の行には、整数T(1≦t≦10000)が含まれています.テスト例の数です.各試験例の第1行は、2つの整数nおよびm(1≦n≦105;0≦m≦109)--都市および市民の数を含む.各試験例の2行目はn整数p 1,p 2,...,を含む.pn(0≦pi≦m;p 1+p 2+…)+pn=MP 1+p 2+…+pn=m)のうち、pipiは第2都市に居住する人数である.3行目はnn個の整数h 1,h 2,....hh 1,h 2,...,HN(−109≦hi≦109−109≦hi≦109)は,hiがi番目の都市の計算幸福指数である.次にn−1行は、道路の説明を含み、各行に1本である.各線は、xiとyi(1≦xi,yi≦n;xi≠yi)の2つの整数を含み、xiとyiはi番目の道路で接続された都市である.すべての試験例からのnの和が2⋅105を超えないことを保証する.
サンプルを入力:
：
2
7 4
1 0 1 1 0 1 0
4 0 0 -1 0 -1 0
1 2
1 3
1 4
3 5
3 6
3 7
5 11
1 2 5 2 1
-11 -2 -6 -2 -1
1 2
1 3
1 4
3 5
：
2
4 4
1 1 1 1
4 1 -3 -1
1 2
1 3
1 4
3 13
3 3 7
13 1 4
1 2
1 3 出力:
各試験例について、収集したデータが正しい場合は「YES」を印刷する.そうでなければ、「NO」の文字.
出力サンプル:
：
YES
YES
：
NO
NO 問題:
dfs
都市xに住む人はp[x]個,計測器指数はh[x]であり,この都市を通る総数はa[x]である.気持ちの良い人はgood[x]人がいて、気持ちの悪い人はbad[x]人がいます
したがって、a[x]=good[x]+bad[x],h[x]=good[x]-bad[x]
3つの制約があります.
1.a[x]+h[x]は2で割り切れる.
2.good[x]の区間範囲は[0,a[x]];
3.親ノード都市の気分が良い人は子ノード都市の気分が良い人より大きい(この都市を通ると気分が悪くなるかもしれないが、良くならない)
コード:
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e6 + 5;
int p[maxn], h[maxn], a[maxn], b[maxn];//a[x] x ,b[x] x ，h[x] x
bool flag = true;
vector<int>g[maxn];
void dfs(int x, int fa) {
a[x] = p[x];
int sum_b = 0;
for (int i = 0; i < g[x].size(); i++) {
int v = g[x][i];
if (v == fa)continue;
dfs(v, x);
a[x] += a[v];
sum_b += b[v];
}
if ((a[x] + h[x]) % 2)flag = false;
b[x] = (a[x] + h[x]) / 2;
if (b[x]<0 || b[x]>a[x])flag = false;
if (sum_b > b[x])flag = false;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)g[i].clear();
for (int i = 1; i <= n; i++)cin >> p[i];
for (int i = 1; i <= n; i++)cin >> h[i];
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
flag = true;
dfs(1, -1);
if (flag)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}