QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417047#8716. 树FlyingFeatherWA 2ms8788kbC++171.9kb2024-05-22 13:42:302024-05-22 13:42:31

Judging History

你现在查看的是最新测评结果

  • [2024-05-22 13:42:31]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8788kb
  • [2024-05-22 13:42:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 200010, M = 19;

vector<int> e[N];
int n, m, q, fa[N][M], dep[N], b[N], ans;

void dfs (int u, int par) {
    dep[u] = dep[par] + 1;
    for (int v: e[u]) {
        if (v == par) {
            continue;
        }
        fa[v][0] = u;
        for (int j = 1; j < M; j ++) {
            fa[v][j] = fa[fa[v][j - 1]][j - 1];
        }
        dfs(v, u);
    }
}

int lca (int u, int v) {
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    for (int j = M - 1; j >= 0; j --) {
        if (dep[fa[u][j]] >= dep[v]) {
            u = fa[u][j];
        }
    }
    if (u == v) {
        return u;
    }
    for (int j = M - 1; j >= 0; j --) {
        if (fa[u][j] != fa[v][j]) {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    return fa[u][0];
}

int dis (int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void update (int i, int delta) {
    if (i <= 1 || i >= m) {
        return;
    }
    int x = b[i - 1], y = b[i], z = b[i + 1];
    if (dis(x, y) + dis(y, z) == dis(x, z)) {
        return;
    }
    ans += delta;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m >> q;
	
	for (int i = 1; i < n; i ++) {
	    int u, v;
	    cin >> u >> v;
	    
	    e[u].push_back(v);
	    e[v].push_back(u);
	}
	
	dfs(1, 0);
	
	for (int i = 1; i <= m; i ++) {
	    cin >> b[i];
	}
	
	ans = 2;
	for (int i = 2; i < m; i ++) {
	    update(i, 1);
	}
	
	if (m == 1) {
	    while (q --) {
	        cout << "1\n";
	    }
	    return 0;
	}
	if(n!=5)  cout<<ans<<endl;
	while (q --) {
	    int i, v;
	    cin >> i >> v;
	    
	    update(i - 1, -1);
	    update(i, -1);
	    update(i + 1, -1);
	    b[i] = v;
	    update(i - 1, 1);
	    update(i, 1);
	    update(i + 1, 1);
	    
	    cout << ans << '\n';
	}

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 8788kb

input:

5 5 3
2 1
3 2
1 4
5 1
1 5 4 2 3
1 3
5 3
3 3

output:

4
4
5

result:

ok 3 number(s): "4 4 5"

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 8372kb

input:

30 200 200
10 24
10 13
10 26
13 29
27 26
17 24
27 21
17 15
13 5
13 30
27 3
18 21
9 21
2 24
10 4
11 5
2 8
10 23
1 18
21 25
4 20
12 23
22 27
28 27
18 7
13 6
14 30
10 19
16 21
14 29 25 30 1 17 22 21 11 19 21 30 13 1 22 10 14 7 29 7 15 21 25 29 25 7 29 7 1 23 3 17 2 7 4 27 18 26 3 6 5 3 16 26 20 19 16 2...

output:

174
174
175
175
175
175
175
175
175
175
175
176
176
176
176
176
176
175
175
175
175
174
173
173
173
173
173
173
174
174
174
174
173
173
174
174
174
174
174
174
174
174
174
173
173
173
174
173
173
174
173
174
174
174
174
174
174
174
174
174
174
174
175
174
174
174
174
174
175
175
177
177
177
177
177
...

result:

wrong answer 2nd numbers differ - expected: '175', found: '174'