QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#770405 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | PatrickStar | 0 | 0ms | 0kb | C++14 | 4.7kb | 2024-11-21 21:43:13 | 2024-11-21 21:43:13 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2e5;
int n, q;
vector<int> v[MAXN+5];
int fa[MAXN+5], dep[MAXN+5], siz[MAXN+5], heavy[MAXN+5], top[MAXN+5];
void d(int i) {
siz[i] = 1;
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]) {
fa[v[i][p]] = i;
dep[v[i][p]] = dep[i]+1;
d(v[i][p]);
siz[i]+=siz[v[i][p]];
if (siz[v[i][p]]>siz[heavy[i]]) heavy[i] = v[i][p];
}
}
return ;
}
int st[MAXN+5], en[MAXN+5], dfn[MAXN+5], tot;
void df(int i, int last) {
st[i] = ++tot;
dfn[tot] = i;
top[i] = last;
if (heavy[i]) df(heavy[i], last);
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) df(v[i][p], v[i][p]);
}
en[i] = tot;
return ;
}
struct e{
int id, k, x;
};
vector<e> d1[MAXN+5], d2[MAXN+5], d3[MAXN+5];
int ans[MAXN+5];
#define lowbit(x) ((x)&(-(x)))
int T[MAXN+5];
void insert(int i, int x) {
i++;
while (i<=n) {
T[i]+=x;
i+=lowbit(i);
}
return ;
}
int found(int i) {
i++;
int u = 0;
while (i) {
u+=T[i];
i-=lowbit(i);
}
return u;
}
void dfs(int i, bool keep) {
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) dfs(v[i][p], 0);
}
if (heavy[i]) dfs(heavy[i], 1);
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) {
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]], 1);
}
}
}
for (int p=0;p<d1[i].size();p++) {
ans[d1[i][p].id]+=d1[i][p].x*found(dep[i]+d1[i][p].k);
}
insert(dep[i], 1);
if (!keep) {
for (int p=st[i];p<=en[i];p++) {
insert(dep[dfn[p]], -1);
}
}
return ;
}
void rec(int i) {
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) {
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]]-dep[i], 1);
}
}
}
for (int p=0;p<d2[i].size();p++) {
ans[d2[i][p].id]+=d2[i][p].x*found(d2[i][p].k);
}
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]) rec(v[i][p]);
}
for (int p=0;p<v[i].size();p++) {
if (v[i][p]!=fa[i]&&v[i][p]!=heavy[i]) {
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]]-dep[i], -1);
}
}
}
return ;
}
bool vis[MAXN+5];
int SIZ, rt, maxp[MAXN+5];
void getrt(int i, int last) {
siz[i] = 1, maxp[i] = 0;
st[i] = ++tot;
dfn[tot] = i;
for (int p=0;p<v[i].size();p++) {
if (!vis[v[i][p]]&&v[i][p]!=last) {
dep[v[i][p]] = dep[i]+1;
getrt(v[i][p], i);
siz[i]+=siz[v[i][p]];
maxp[i] = max(maxp[i], siz[v[i][p]]);
}
}
en[i] = tot;
maxp[i] = max(maxp[i], SIZ-siz[i]);
if (maxp[i]<maxp[rt]) rt = i;
return ;
}
void divide(int i) {
vis[i] = 1;
insert(0, 1);
for (int p=0;p<v[i].size();p++) {
if (!vis[v[i][p]]) {
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]]-dep[i], 1);
}
}
}
for (int p=0;p<v[i].size();p++) {
if (!vis[v[i][p]]) {
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]]-dep[i], -1);
}
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
int s = dfn[k];
for (int j=0;j<d3[s].size();j++) {
ans[d3[s][j].id]+=d3[s][j].x*found(d3[s][j].k-(dep[s]-dep[i]));
}
}
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]]-dep[i], 1);
}
}
}
insert(0, -1);
for (int p=0;p<d3[i].size();p++) {
ans[d3[i][p].id]+=d3[i][p].x*found(d3[i][p].k);
}
for (int p=0;p<v[i].size();p++) {
if (!vis[v[i][p]]) {
for (int k=st[v[i][p]];k<=en[v[i][p]];k++) {
insert(dep[dfn[k]]-dep[i], -1);
}
}
}
for (int p=0;p<v[i].size();p++) {
if (!vis[v[i][p]]) {
SIZ = siz[v[i][p]];
rt = 0;
getrt(v[i][p], 0);
dep[rt] = 0;
tot = 0;
getrt(rt, 0);
divide(rt);
}
}
return ;
}
int main() {
scanf("%d", &n);
for (int p=1;p<n;p++) {
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
d(1);
df(1, 1);
scanf("%d", &q);
for (int p=1;p<=q;p++) {
int x, y, k;
scanf("%d %d %d", &x, &y, &k);
while (top[x]!=top[y]) {
if (dep[top[x]]>dep[top[y]]) swap(x, y);
d1[y].push_back({p, k, 1});
d1[top[y]].push_back({p, k-1, -1});
d2[fa[y]].push_back({p, k, 1});
d2[fa[top[y]]].push_back({p, k, -1});
ans[p]+=dep[y]-dep[top[y]]+1;
y = fa[top[y]];
}
if (dep[x]>dep[y]) swap(x, y);
ans[p]+=dep[y]-dep[x]+1;
if (x!=y) {
d1[y].push_back({p, k, 1});
d2[fa[y]].push_back({p, k, 1});
d2[x].push_back({p, k, -1});
}
d1[x].push_back({p, k, -1});
d2[x].push_back({p, k, 1});
d2[fa[x]].push_back({p, k, -1});
d3[x].push_back({p, k, 1});
}
dfs(1, 0);
rec(1);
SIZ = maxp[0] = n;
getrt(1, 0);
dep[rt] = 0;
tot = 0;
getrt(rt, 0);
divide(rt);
for (int p=1;p<=q;p++) {
printf("%d\n", ans[p]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
result:
Subtask #2:
score: 0
Runtime Error
Test #9:
score: 0
Runtime Error
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Test #25:
score: 0
Runtime Error
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%