QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#418959 | #8716. 树 | paoxiaomo# | WA | 0ms | 7700kb | C++20 | 6.5kb | 2024-05-23 16:40:58 | 2024-05-23 16:40:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
// #define max(a, b) ((a) > (b) ? (a) : (b))
// #define min(a, b) ((a) < (b) ? (a) : (b))
#define pb push_back
#define LNF 1e18
#define INF 0x7fffffff
#define int long long
#define lowbit(x) ((x) & (-x))
#define abs(x) llabs(x)
#define endl '\n'
#define Y() cout << "Yes" << endl
#define N() cout << "No" << endl
const db eps = 1e-9;
const int MOD = 1e9 + 7;
const int MAXN = 2e5 + 5;
vector<int> pth[200005];
int b[200005], add[200005], f[200005];
struct RMQ
{ // 求序列中区间最大?最小值的下标
int n;
vector<int> lg, nu;
vector<array<int, 25>> dp; // 固定内部数组降低常数
int get(const int &a, const int &b)
{
return nu[a] < nu[b] ? a : b; // 自定义比较函数,返回在原数组中较大的下标
}
RMQ() {}
RMQ(vector<int> &v)
{ // v的有效下标从1开始,v.size()-1结束
n = v.size() - 1;
nu = v;
lg.resize(n + 1);
dp.resize(n + 1);
lg[1] = 0;
for (int i = 2; i <= n; i++)
{
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1; i <= n; i++)
{
dp[i][0] = i;
}
for (int j = 1; j <= lg[n]; j++)
{
for (int i = 1; i <= n - (1 << j) + 1; i++)
{
dp[i][j] = get(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
int getidex(const int &l, const int &r) // 返回最值下标
{
int len = lg[r - l + 1];
return get(dp[l][len], dp[r - (1 << len) + 1][len]);
}
int getnum(const int &l, const int &r) // 返回最值
{
return nu[getidex(l, r)];
}
};
struct GRAPH
{
vector<vector<pair<int, int>>> pth;
vector<int> dep, first, nu, ref;
int cnt = 0;
GRAPH(int n)
{
pth.resize(n + 1);
dep.resize(n + 1);
first.resize(n + 1);
nu.resize(n * 2 + 1);
ref.resize(n * 2 + 1);
cnt = 0; // 构造好了以后直接加边
}
void add_edge(int u, int v, int w = 1)
{ // 加双向边
pth[u].push_back({v, w});
pth[v].push_back({u, w});
}
void dfs(int pos, int fa)
{
first[pos] = ++cnt; // 第一次碰到这个点的dfs序
nu[cnt] = dep[pos]; // 这个dfs序的深度
ref[cnt] = pos;
for (auto [to, len] : pth[pos])
{
if (to == fa)
continue;
dep[to] = dep[pos] + len; // 当前点深度
dfs(to, pos);
nu[++cnt] = dep[pos];
ref[cnt] = pos;
}
};
RMQ rmq;
void prepare(int st)
{ // st是树的根节点
dfs(st, 0);
rmq = RMQ(nu);
}
int query_lca(int x, int y)
{ // 询问两点间的最近公共祖先
int l, r;
l = first[x], r = first[y];
if (l > r)
swap(l, r);
int t = rmq.getidex(l, r);
int lca = ref[t];
return lca;
};
int query_dis(int x, int y)
{ // 询问两点间的距离
int len = dep[x] + dep[y] - 2 * dep[query_lca(x, y)];
return len;
};
};
void solve()
{
int n, m, q;
cin >> n >> m >> q;
GRAPH g(n + 1);
for (int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g.add_edge(u, v);
}
g.prepare(1);
int ans = 2, fore = 0, flag = 0;
for (int i = 1; i <= m; i++)
{
cin >> b[i];
}
auto cal = [&](int i) -> void
{
if (i == 2)
{
int lc = g.query_lca(b[2], b[1]);
if (lc == b[2])
{
fore = 1;
}
else
{
fore = -1;
}
return;
}
f[i] = fore;
int lca = g.query_lca(b[i], b[i - 1]);
// cout << lca << endl;
// cout << fore << " ";
if (lca == b[i] || lca == b[i - 1])
{
// cout << i << endl;
if (g.dep[b[i]] > g.dep[b[i - 1]])
{
flag = -1;
}
else
{
flag = 1;
}
if (fore != flag)
ans++, add[i]++;
fore = flag;
// cout << ans << endl;
}
else
{
ans++, add[i]++;
flag = 1;
fore = -1;
}
};
auto cal1 = [&](int i) -> void
{
if (i == 2)
{
int lc = g.query_lca(b[2], b[1]);
if (lc == b[2])
{
fore = 1;
}
else
{
fore = -1;
}
f[i + 1] = fore;
return;
}
add[i] = 0;
fore = f[i];
int lca = g.query_lca(b[i], b[i - 1]);
// cout << lca << endl;
// cout << fore << " ";
if (lca == b[i] || lca == b[i - 1])
{
// cout << i << endl;
if (g.dep[b[i]] > g.dep[b[i - 1]])
{
flag = -1;
}
else
{
flag = 1;
}
if (fore != flag)
ans++, add[i]++;
fore = flag;
// cout << ans << endl;
}
else
{
ans++, add[i]++;
flag = 1;
fore = -1;
}
f[i + 1] = fore;
};
for (int i = 2; i <= m; i++)
{
cal(i);
cout << ans << endl;
}
// cout << endl;
// f[m + 1] = fore;
// if (f[m + 1] != 0)
// ans++;
// for (int i = 1; i <= m; i++)
// cout << add[i] << " ";
// cout << endl;
// cout << ans << endl;
while (q--)
{
int p, w;
cin >> p >> w;
if(m==1||m==2){
cout<<m<<endl;continue;
}
ans -= (add[p] + add[p + 1] + add[p + 2]);
// if (f[m + 1] != 0)
// ans--;
b[p] = w;
if (p != 1)
{
cal1(p);
}
if (p + 1 <= m)
cal1(p + 1);
if (p + 2 <= m)
cal1(p + 2);
cout << ans << endl;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7700kb
input:
5 5 3 2 1 3 2 1 4 5 1 1 5 4 2 3 1 3 5 3 3 3
output:
2 3 4 4 4 4 5
result:
wrong answer 1st numbers differ - expected: '4', found: '2'