uva 699 uva 839 귀속 트리

uva 839일 Not so Mobile
링크 스탬프 여기에 나무 모양의 천평을 입력하여 모멘트가 같음에 따라 균형 여부를 판단합니다.모멘트가 같으면 Wl * Dl = Wr * Dr입니다. 먼저 이 트리를 입력하십시오.만약에 Wl 또는 Wr가 0이라면 이 분동이 자천평이라는 것을 대표한다. 다음에 이 자천평을 묘사할 것이다. 둘 다 0일 때 왼쪽 자천평을 먼저 묘사하고 오른쪽 자천평을 묘사할 것이다.
주의해야 할 점: 먼저 두루 돌아다니기 때문에 좌우 나무의 무게를 알 수 없기 때문에 인용으로 무게를 얻을 수 있다.좌우 자목의 무게를 얻은 후 모멘트가 같은지 아닌지를 판단한다.그러나 나무 전체의 균형은 왼쪽 균형과 오른쪽 균형, 뿌리 균형이라는 것을 잊지 마라.또한 출력 형식은 한 그룹 사이의 공백을 조심해야 한다.합법적인 나무이기 때문에 입력한 그룹과 그룹 사이에는 특별한 판단이 필요 없습니다.

#include 
#include 
using namespace std;

const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
int N, M;

bool solve(int &w) {
    int wl, dl, wr, dr;
    scanf("%d %d %d %d", &wl, &dl, &wr, &dr);
    bool okl = 1, okr = 1;
    if (!wl) okl = solve(wl);
    if (!wr) okr = solve(wr);
    w = wl + wr;
    return okl && okr && wl * dl == wr * dr;
}

int main() {
    int T, w;
    scanf("%d", &T);
    while (T--) {
        puts(solve(w) ? "YES" : "NO");
        if (T)
            puts("");
    }
    return 0;
}

uva 699 The Falling Leaves
링크 스탬프 여기 두 갈래 나무 하나 주세요.왼쪽 노드는 루트의 왼쪽 1 단위, 오른쪽 노드는 루트의 오른쪽 1 단위입니다.왼쪽에서 오른쪽으로 수직 방향의 모든 노드 값의 합을 출력합니다.

    5
   / \
  7   3
   \
    6

전례대로 7, 11, 3을 출력해야 하는데 언뜻 보기에는 좀 까다롭다.그러나 나무의 관계를 하나의 수조에 놓고 좌우 인-1의 상대적인 관계를 이용하여 나무를 세우자 갑자기 밝아졌다.

#include 
#include 
using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
const int inf = 0x3f3f3f3f, maxN = 2001;
int N, M;
int sum[maxN];

void build(int rt) {
    int v;
    scanf("%d", &v);
    if (v == -1)
        return;
    sum[rt] += v;
    build(rt - 1);
    build(rt + 1);
}
bool init() {
    int v;
    scanf("%d", &v);
    if (v == -1)
        return 0;
    mst(sum, 0);
    int rt = maxN / 2;
    sum[rt] += v;
    build(rt - 1);
    build(rt + 1);
    return 1;
}

int main() {
    int T = 0;
    while (init()) {
        ++T;
        int cur = 0;
        while (sum[cur] == 0)
            ++cur;
        printf("Case %d:
", T);
        int fg = 0;
        while (sum[cur] != 0) {
            if (!fg) fg = 1;
            else printf(" ");
            printf("%d", sum[cur++]);
        }
        puts("
");
    }
    return 0;
}