QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108593 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | Forza_Ferrari | 0 | 0ms | 0kb | C++14 | 3.4kb | 2023-05-25 17:30:10 | 2023-05-25 17:30:13 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n,m,ans[3000001],dep[3000001],fa[3000001],s[3000001],son[3000001],top[3000001],dfn[3000001],sum[3000005],cnt;
struct element
{
int x,y,k,id;
}q[3000001];
vector<int> v[3000001];
struct opt
{
int k,tag,id;
opt(int k_,int tag_,int id_):
k(k_),tag(tag_),id(id_){}
};
vector<opt> a[3000001];
struct ds
{
int len[3000001],son[3000001],tmp[3000001],*id=tmp,*sum[3000001];
vector<int> a[3000001],b[3000001];
inline void dfs1(int k,int f)
{
for(int i:v[k])
{
if(i==f)
continue;
dfs1(i,k);
if(len[i]>len[k])
{
len[k]=len[i];
son[k]=i;
}
}
++len[k];
}
inline void dfs2(int k,int f)
{
if(son[k])
{
sum[son[k]]=sum[k]+1;
dfs2(son[k],k);
}
sum[k][0]+=s[k];
for(int i:v[k])
{
if(i==f||i==son[k])
continue;
sum[i]=id;
id+=len[i];
dfs2(i,k);
for(int j=0;j<len[i];++j)
sum[k][j+1]+=sum[i][j];
}
for(int i:a[k])
{
ans[i]+=s[k];
if(q[i].k+1<len[k])
ans[i]-=sum[k][q[i].k+1];
if(fa[top[k]]&&dep[fa[top[k]]]>=dep[q[i].x])
a[fa[top[k]]].emplace_back(i);
}
for(int i:b[k])
{
ans[i]-=s[k];
if(q[i].k<len[k])
ans[i]+=sum[k][q[i].k];
if(fa[top[fa[k]]]&&dep[fa[top[fa[k]]]]>=dep[q[i].x])
b[top[fa[k]]].emplace_back(i);
}
a[k].clear();
a[k].shrink_to_fit();
b[k].clear();
b[k].shrink_to_fit();
}
}T;
inline void dfs1(int k,int f,int deep)
{
dep[k]=deep;
fa[k]=f;
s[k]=1;
for(int i:v[k])
{
if(i==f)
continue;
dfs1(i,k,deep+1);
s[k]+=s[i];
if(s[i]>s[son[k]])
son[k]=i;
}
}
inline void dfs2(int k,int t)
{
top[k]=t;
dfn[k]=++cnt;
if(!son[k])
return;
dfs2(son[k],t);
for(int i:v[k])
{
if(i==fa[k]||i==son[k])
continue;
dfs2(i,i);
}
}
inline void update(int x,int y,int k,int id)
{
T.a[y].emplace_back(id);
if(x==y)
return;
bool flag=0;
while(y==top[y])
{
if(!flag)
{
flag=1;
T.b[y].emplace_back(id);
}
y=fa[y];
if(y==x)
return;
}
y=fa[y];
while(top[x]^top[y])
{
a[y].emplace_back(k,1,id);
y=top[y];
while(y==top[y])
{
if(!flag)
{
flag=1;
T.b[y].emplace_back(id);
}
y=fa[y];
if(y==x)
return;
}
y=fa[y];
}
a[y].emplace_back(k,1,id);
if(x!=top[x])
a[fa[x]].emplace_back(k,-1,id);
}
inline void dfs(int k,int f,int deep,int p)
{
sum[deep]+=p*s[k];
for(int i:v[k])
{
if(i==f)
continue;
dfs(i,k,deep+1,p);
}
}
inline void init()
{
ios::sync_with_stdio(0);
cin.tie(0);
}
inline int read()
{
int x;
cin>>x;
return x;
}
int main()
{
init();
n=read();
for(int i=2;i<=n;++i)
{
int f=read();
v[f].emplace_back(i);
v[i].emplace_back(f);
}
dfs1(1,0,1);
dfs2(1,1);
m=read();
for(int i=1;i<=m;++i)
{
q[i].x=read(),q[i].y=read(),q[i].k=read();
update(q[i].x,q[i].y,q[i].k,q[i].id=i);
}
T.dfs1(1,0);
T.sum[1]=T.id;
T.id+=T.len[1];
T.dfs2(1,0);
for(int i=1;i<=n;++i)
if(top[i]==i)
{
int res=0;
for(int j=i;j;j=son[j])
{
++res;
for(int k:v[j])
if(k!=son[j]&&k!=fa[j])
{
res+=s[k];
dfs(k,j,1,1);
}
for(auto k:a[j])
ans[k.id]+=k.tag*(res-sum[k.k+1]);
}
for(int j=i;j;j=son[j])
for(int k:v[j])
if(k!=son[j]&&k!=fa[j])
dfs(k,j,1,-1);
}
for(int i=1;i<=m;++i)
cout<<ans[i]<<'\n';
cout.flush();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
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
Time Limit Exceeded
Test #9:
score: 0
Time Limit Exceeded
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
Time Limit Exceeded
Test #25:
score: 0
Time Limit Exceeded
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%