11503번: Tree Edit

https://www.acmicpc.net/problem/11503

T1, T2의 각 노드에 서로 다른 번호가 부여되어 있다고 하자.
i번 노드의 자식들을 ci_1, ci_2, ...라고 하자.
ed[i][j]: i번 노드가 루트인 T1의 서브트리를 j번 노드가 루트인 T2의 서브트리로 바꾸는데 필요한 최소 편집 연산 수
ed[i][j]는 ed[ci_1..n][cj_1..m]들을 가지고 DP로 구할 수 있다.

dp[u][v]: ci_1..u 를 cj_1..v로 바꾸는데 필요한 최소 편집 연산 수
dp[u][v] = min(
dp[u-1][v] + (ci_u가 루트인 서브트리의 사이즈),
dp[u][v-1] + (cj_v가 루트인 서브트리의 사이즈),
dp[u-1][v-1] + ed[ci_u][cj_v])
그러면 ed[i][j]는 dp[n][m]이 된다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int tc, ed[2000][2000], sz[2000], pos, id;
char la[2000], s[3001];
vector<int> adj[2000];
int f(int l, int r) {
    if (~ed[l][r]) return ed[l][r];
    int n = adj[l].size(), m = adj[r].size();
    vector<vector<int> > dp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++) dp[i][0] = dp[i - 1][0] + sz[adj[l][i - 1]];
    for (int i = 1; i <= m; i++) dp[0][i] = dp[0][i - 1] + sz[adj[r][i - 1]];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
        dp[i][j] = min({ dp[i][j - 1] + sz[adj[r][j - 1]],
            dp[i - 1][j] + sz[adj[l][i - 1]],
            dp[i - 1][j - 1] + f(adj[l][i - 1], adj[r][j - 1]) });
    return ed[l][r] = dp[n][m] + (la[l] != la[r]);
}
void gen() {
    int h = id++, st = pos;
    adj[h].clear();
    la[h] = s[++pos];
    while (s[++pos] != ')') adj[h].push_back(id), gen();
    sz[h] = (pos - st) / 3 + 1;
}
void solve() {
    fill(&ed[0][0], &ed[1999][2000], -1);
    scanf("%s", s); id = pos = 0; gen();
    int t = id;
    scanf("%s", s); pos = 0; gen();
    printf("%d\n", f(0, t));
}
int main() {
    for (scanf("%d", &tc); tc--;) solve();
    return 0;
}

1068번: 트리

https://www.acmicpc.net/problem/1068

indegree를 카운트해서 리프 노드인지 판단한다.
리프 노드로부터 거슬러 올라가다가 제거한 노드를 만나면 해당 노드는 제거된다.
아래 소스의 시간복잡도 $O(n^2)$

#include<cstdio>
int n, p[50], ind[50], g, c;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", p + i);
        if (~p[i]) ind[p[i]]++;
    }
    scanf("%d", &g);
    for (int i = 0; i < n; i++) if (!ind[i]) for (int j = i; ~j; j = p[j]) if (j == g) { c++; break; }
    printf("%d", n / 2 + 1 - c);
    return 0;
}

13325번: Binary Tree

https://www.acmicpc.net/problem/13325

깊은 노드부터 부모로 올라가며 자신 - 단말 노드 거리가 일치하도록 자식과의 거리를 조절한다.
아래 소스의 시간복잡도는 $O(2^k)$

#include<cstdio>
#include<algorithm>
using namespace std;
int k, a[1 << 21], r, i, t;
int main() {
    scanf("%d", &k);
    for (i = 2; i < 1 << k + 1; i++) scanf("%d", a + i);
    while (i -= 2) r += t = max(a[i], a[i + 1]), a[i / 2] += t;
    printf("%d", r + t);
    return 0;
}

2533번: 사회망 서비스(SNS)

https://www.acmicpc.net/problem/2533


$O(n)$

1번 정점이 root인 rooted tree를 만들어보자.
자식노드 중 얼리어 답터가 아닌 노드가 있으면 해당 노드는 얼리어 답터이어야 한다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e6;
int n, ck[MXN + 1], res;
vector<int> adj[MXN + 1];
void f(int h, int p) {
    int flag = 0;
    for (auto it : adj[h]) if (it^p) {
        f(it, h);
        flag |= !ck[it];
    }
    if (flag) ck[h] = 1, res++;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    printf("%d", res);
    return 0;
}

11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

$O(n)$

#include<cstdio>
#include<vector>
using namespace std;
int n, p[100001];
vector<int> adj[100001];
void f(int h) {
    for (auto it : adj[h]) if (p[h] ^ it) p[it] = h, f(it);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    for (int i = 2; i <= n; i++) printf("%d\n", p[i]);
    return 0;
}

8872번: 빌라봉

https://www.acmicpc.net/problem/8872


$O(n+m)$

트리에서 나머지 지점까지의 거리의 최댓값이 최소가 되는 지점을 중심이라 하고 그 값을 반지름이라 하자.
반지름이 최대인 트리의 중심에 나머지 트리의 중심을 이어주면 된다.

따라서 답은 다음 가능한 경우 중 최댓값이다.

1. 트리의 최대 지름
2. 최대 반지름 + 두번째 반지름 + L
3. 두번째 반지름 + 세번째 반지름 + L*2

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, m, l, d[MXN], ck[MXN], r;
vector<pair<int, int> > adj[MXN];
void f(int h) {
    ck[h] = 1;
    for (auto it : adj[h]) if (!ck[it.first]) {
        f(it.first);
        d[h] = max(d[h], d[it.first] + it.second);
    }
}
int g(int h, int pl) {
    int m1 = pl, m2 = 0, t = 2e9;
    ck[h] = 0;
    for (auto it : adj[h]) if (ck[it.first]) {
        m2 = max(m2, d[it.first] + it.second);
        if (m1 < m2) swap(m1, m2);
    }
    r = max(r, m1 + m2);
    for (auto it : adj[h]) if (ck[it.first]) t = min(t, g(it.first, (m1 == d[it.first] + it.second ? m2 : m1) + it.second));
    return min(m1, t);
}
int main() {
    scanf("%d%d%d", &n, &m, &l);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
        adj[y].push_back({ x,z });
    }
    for (int i = 0; i < n; i++) if (!ck[i]) f(i);
    int m[3] = { -1000000000,-1000000000 };
    for (int i = 0; i < n; i++) if (ck[i]) {
        m[2] = max(m[2], g(i, 0));
        for (int j = 3; --j;) if (m[j] > m[j - 1]) swap(m[j], m[j - 1]);
    }
    printf("%d", max({ r,m[0] + m[1] + l,m[1] + m[2] + l * 2 }));
    return 0;
}

12817번: 버스 노선

https://www.acmicpc.net/problem/12817


$O(n)$

아무 노드 하나를 루트로 하는 rooted tree를 만든다.
r[i]: i번 버스 정류장에 멈추는 버스의 수
aj: i번 노드의 j(<=m)번째 자식의 자손 수
sj=sum(a[1...j])

r[i]={sum((sj+1)*a[j])+(sm+1)*(n-sm-1)}*2 이다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 1e6;
typedef long long ll;
int n;
vector<int> adj[MXN + 1];
ll r[MXN + 1];
int f(int h, int p) {
    ll s = 1;
    for (auto it : adj[h]) if (it^p) {
        int t = f(it, h);
        r[h] += s*t;
        s += t;
    }
    r[h] += s*(n - s);
    return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i<n - 1; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    for (int i = 1; i <= n; i++) printf("%lld\n", r[i] * 2);
    return 0;
}

11812번: K진 트리

https://www.acmicpc.net/problem/11812


$O(q\lg _k{n})$

노드 번호가 1번부터 시작한다면 x의 부모는 (x-2)/k+1
두 노드의 공통 조상을 찾기 위해선 큰 번호의 노드를 부모로 거슬러 올리는 것을 반복하면 된다.
k=1인 경우에 이 방법으로는 시간초과가 날 수 있으므로 따로 처리해야한다.

#include<cstdio>
#include<algorithm>
using namespace std;
long long n, x, y;
int k, q;
int main() {
    scanf("%d%d%d", &n, &k, &q);
    for (; q--;) {
        scanf("%lld%lld", &x, &y);
        if (k<2) {
            printf("%lld\n", abs(x - y));
            continue;
        }
        int r = 0;
        while (x^y) {
            if (x<y) swap(x, y);
            x = (x - 2) / k + 1;
            r++;
        }
        printf("%d\n", r);
    }
    return 0;
}

2454번: 트리 분할

https://www.acmicpc.net/problem/2454


$O(n)$

트리 내의 아무 정점에서 dfs탐색을 시작해보자.
이 문제는 탐색과정에서 (x,y)=(k+1개 커버 중 남은 개수, 분할 수) 정보만 가지고 해결할 수 있다.
* k+1개 커버 중 남은 개수란 앞으로 같은 묶음으로 포함할 수 있는 조상 정점들의 개수이다.
이게 가능한 이유는 다음과 같다.
현재 정점과 그 자식들을 포함한 트리의 가능한 (x,y) 해가 (x1,y1), (x2,y2) .. 있다고 해보자.
(xi,yi)와 (xj,yj) 중 어떤게 더 나은 해인지 판단하기 위해 다음 경우들을 따져보면 된다.
yi<yj일 때,
xi>xj 당연히 xi는 xj처럼 덜 쓸 수 있기때문에 전자가 유리하다.
xi<xj xi가 더 작지만 yi+1을 하여 xi=k>=xj 로 만들 수 있어 전자가 유리하다.
yi=yj일 때,
xi, xj 중 큰 쪽이 유리하다.
결론적으로 y가 작은 경우, 같다면 x가 큰 경우가 트리의 모양과 상관 없이 항상 유리하므로 해가 하나로 결정된다.

현재 정점의 (x,y)는 다음과 같이 결정한다.
자식들의 (x,y)를 (xi,yi)라고 표현하고 자식들의 yi 합을 s라고 하자.
가장 큰 자식들의 두 x 값을 p,q(p>q)라 하면
p+q>k+1인 경우 현재 정점을 조상과 같이 묶지 않고 자식들과 함께 묶음을 형성하여 s-1개의 묶음을 만들 수 있다. 이것은 가장 최선이다. -> (0,s-1) 리턴
그렇지 않고 p가 0보다 크다면 조상으로 나가는 묶음이 존재할 수 있으며(1이 아니면 그렇다) s개의 묶음을 만들 수 있다. -> (p-1,s)리턴
위 경우에 모두 해당되지 않는 경우는 각 자식들이 묶음의 끝이 되는 경우이다.
이 경우, 현재 정점으로부터 새로운 묶음을 형성해야 한다. -> (k,s+1) 리턴

처음 탐색을 시작한 정점이 리턴한 y값이 답이 된다.

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX_N = 3e5;
int n, k;
vector<int> adj[MAX_N + 1];
pair<int, int> dfs(int h, int p) {
    int m1, m2, s;
    m1 = m2 = s = 0;
    for (auto it : adj[h]) {
        if (it == p) continue;
        pair<int, int> p = dfs(it, h);
        m2 = max(m2, p.first);
        if (m1 < m2) swap(m1, m2);
        s += p.second;
    }
    if (m1 + m2 > k + 1) return{ 0,s - 1 };
    if (m1) return{ m1 - 1, s };
    return{ k, s + 1 };
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    printf("%d", dfs(1, -1).second);
    return 0;
}

2970번: 두더지

https://www.acmicpc.net/problem/2970


$O(n)$

먼저, 트리의 지름(트리 상에서 가장 먼 두 정점의 경로)을 구한다.
지름의 끝 정점을 s1, s2라 하자.
s1과 s2를 잇는 경로상의 한 간선을 지워야 한다. 그러지 않는다면, 지름의 값이 가장 먼 두 정점의 거리가 될 것이기 때문이다.
간선을 하나 지웠다고 해보자. 문제는 s1을 포함하는 트리의 지름과 s2를 포함하는 트리의 지름에 의해 답이 결정된다.
s1-a1-a2-a3- ... - an-s2 (ai는 가지를 가질 수도 있다.) 모양에서
s1 ~ ai, ai~s2 트리마다의 지름을 구해야 한다.
이는 s1,s2를 시작 정점으로 하는 dfs 탐색을 이용해 해결할 수 있다.
이에 대해 간략하게 말하면 탐색에서 자신을 끝으로 하는 사슬의 최대 길이와 자식들의 지름을 가지고 갱신시키면 된다.
(본 블로그 내의 트리의 지름 1번 풀이를 참고하자. http://codedoc.tistory.com/240)
a(i-1) 과 ai를 끊었을 때의 최소 거리는 다음 세 값 중 최댓값이다.
1. s1~a(i-1) 상의 지름
2. ai~s2 상의 지름
3. s1~a(i-1) 반지름 + ai~s2 반지름 + 1
최댓값이 가장 작을 때가 답이다.
자를 곳을 결정했다면 그 간선을 제거하고 나눠진 트리에서 각각 중심점을 찾고 이으면 된다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 3e5;
vector<int> adj[MAX_N + 1];
int n, maxi, t, ck[MAX_N + 1];
int vis[MAX_N], vck;
void dfs1(int h, int p, int dep, int v) {
    if (dep > maxi) maxi = dep, t = h;
    ck[h] = 1;
    if (v != -1 && !vck) vis[dep] = h;
    if (h == v) vck = 1;
    for (auto it : adj[h])
        if (!ck[it]) dfs1(it, h, dep + 1, v);
    ck[h] = 0;
}
int l[2][MAX_N + 1];
int dfs2(int h, int p, int idx) {
    int m1 = 0, m2 = 0;
    for (auto it : adj[h]) {
        if (it == p) continue;
        m2 = max(m2, dfs2(it, h, idx) + 1);
        if (m1 < m2) swap(m1, m2);
        l[idx][h] = max(l[idx][h], l[idx][it]);
    }
    l[idx][h] = max(l[idx][h], m1 + m2);
    return m1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, x, y; i < n - 1; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int s1, s2, idx, res = 0x7fffffff;
    maxi = -1; dfs1(1, -1, 0, -1); s1 = t;
    maxi = -1; dfs1(s1, -1, 0, -1); s2 = t;
    dfs2(s2, -1, 0);
    dfs2(s1, -1, 1);
    maxi = -1; dfs1(s1, -1, 0, s2);
    for (int i = 1, tl; i <= maxi; i++) {
        tl = max({ (l[0][vis[i - 1]] + 1) / 2 + (l[1][vis[i]] + 1) / 2 + 1,
            l[0][vis[i - 1]],l[1][vis[i]] });
        if (res > tl) res = tl, idx = i;
    }
    s1 = vis[idx - 1]; s2 = vis[idx];
    int h1, h2, r1, r2;
    ck[s2] = 1;
    maxi = -1; dfs1(s1, -1, 0, -1); h1 = t;
    maxi = -1; dfs1(h1, -1, 0, -1); h2 = t;
    maxi = -1; vck = 0; dfs1(h1, -1, 0, h2); r1 = vis[maxi / 2];
    ck[s2] = 0; ck[s1] = 1;
    maxi = -1; dfs1(s2, -1, 0, -1); h1 = t;
    maxi = -1; dfs1(h1, -1, 0, -1); h2 = t;
    maxi = -1; vck = 0; dfs1(h1, -1, 0, h2); r2 = vis[maxi / 2];
    printf("%d\n%d %d\n%d %d", res, s1, s2, r1, r2);
    return 0;
}

1289번: 트리의 가중치

https://www.acmicpc.net/problem/1289


$O(n)$

한 노드의 자식노드 a1,a2, ... 이 있다 하자.
모든 경우를 따지기 위해선
1. 자식노드 - 현재 노드 - 자식 노드
2. 자식노드 - 현재 노드
이 두 경우를 따져서 가중치를 구해 더하면 된다.

각 자식들로 끝나는 가중치를 bi 라 하자.
2번 케이스는 bi 전체 합을 이용해 쉽게 구할 수 있다.
1번 케이스는 bi-1 까지의 누적 합 곱하기 bi를 누적함으로써 구할 수 있다.

#include<stdio.h>
#include<vector>
#define mod 1000000007
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
vector<pair<int, int> > adj[MAX_N + 1];
int n, res;
int dfs(int h, int p) {
    int s = 1, t;
    for (auto it : adj[h]) {
        if (it.first == p) continue;
        t = (ll)dfs(it.first, h)*it.second%mod;
        res = (res + (ll)t*s) % mod;
        s = (s + t) % mod;
    }
    return s;
}
int main() {
    scanf("%d", &n);
    for (int i = 0, a, b, c; i < n - 1; i++) {
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c });
    }
    dfs(1, -1);
    printf("%d", res);
    return 0;
}