QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#875616 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | duck_pear | 0 | 993ms | 188308kb | C++14 | 6.1kb | 2025-01-29 23:57:10 | 2025-01-29 23:57:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define TY int
#define IL inline
#define pb push_back
#define MAXN 200005
#define mod (TY)(1e9+7)
#define INF (TY)(1e9)
#define For(i,a,b) for(TY i=(a);i<=(b);++i)
#define FOR(i,a,b) for(TY i=(a);i<(b);++i)
#define Rof(i,a,b) for(TY i=(a);i>=(b);--i)
#define ROF(i,a,b) for(TY i=(a);i>(b);--i)
IL TY qr(){
TY u=0,v=1;char ch=getchar();
while(ch>'9'||ch<'0')v=(ch=='-'?-1:1),ch=getchar();
while(ch>='0'&&ch<='9')u=(u*10)+(ch-'0'),ch=getchar();
return u*v;
}IL void qw(TY now){
if(now<0){putchar('-');now=-now;}
if(!now){putchar('0');return;}
if(now>=10)qw(now/10);putchar(now%10+'0');
}IL void qw(TY now,char ch){qw(now);putchar(ch);}
IL bool ischar(char u){return (u>='a'&&u<='z')||(u>='A'&&u<='Z');}
IL char getc(){
char u=getchar();
while(!ischar(u))u=getchar();
return u;
}IL string qs(){
string s="";char ch=getchar();
while(!ischar(ch))ch=getchar();
while(ischar(ch))s+=ch,ch=getchar();
return s;
}IL void ws(string s){FOR(i,0,s.size())putchar(s[i]);}
IL TY Pow(TY a,TY b){
TY ans=1,base=a;
while(b){
if(b&1)ans=ans*base%mod;
base=base*base%mod;b>>=1;
}return ans;
}IL TY Mod(TY u){return (u>=mod?u-mod:u);}
TY n,m,siz[MAXN],deep[MAXN],father[MAXN],son[MAXN],top[MAXN],ans[MAXN],id[MAXN],seg[MAXN],cnt;
TY rt,S,maxx[MAXN];
bool vis[MAXN];
vector<TY> e[MAXN];
struct node{TY d,op,id;};
IL bool cmp(node x,node y){return x.d<y.d;}
vector<node> q1[MAXN],q2[MAXN],q3[MAXN];
IL void Pb(TY i,TY j){e[i].pb(j);e[j].pb(i);}
struct Tree{
TY tree[MAXN];
stack<TY> use;
IL void clear(){
while(!use.empty())tree[use.top()]=0,use.pop();
}IL void add(TY now,TY w){
++now;
while(now<=n+1){
tree[now]+=w;
use.push(now);
now+=(now&-now);
}
}IL TY query(TY now){
++now;
TY sum=0;
while(now){
sum+=tree[now];
now-=(now&-now);
}return sum;
}IL TY query(TY l,TY r){
if(l>r)return 0;
else return query(r)-query(l-1);
}
}tr;
void dfs1(TY now,TY fa){
TY nowson=-1;
siz[now]=1;
deep[now]=deep[fa]+1;
father[now]=fa;
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==fa)continue;
dfs1(y,now);
siz[now]+=siz[y];
if(siz[y]>nowson){nowson=siz[y];son[now]=y;}
}
}void dfs2(TY now,TY topf){
id[now]=++cnt;
seg[cnt]=now;
top[now]=topf;
if(!son[now])return;
dfs2(son[now],topf);
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==father[now]||y==son[now])continue;
dfs2(y,y);
}
}TY LCA(TY x,TY y){
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]])swap(x,y);
x=father[top[x]];
}if(deep[x]>deep[y])swap(x,y);
return x;
}void query(TY u,TY v,TY d,TY id){
TY z=LCA(u,v);
if(u!=z)q2[u].pb({d,1,id});
if(v!=z)q2[v].pb({d,1,id});
while(top[u]!=top[v]){
if(deep[top[u]]<deep[top[v]])swap(u,v);
q1[father[u]].pb({d,1,id});
q1[father[top[u]]].pb({d,-1,id});
u=top[u];
if(father[u]!=z){
q2[father[u]].pb({d,1,id});
q2[u].pb({d-1,-1,id});
}else q2[u].pb({d-1,-1,id});
u=father[u];
}if(deep[u]>deep[v])swap(u,v);
if(u!=v){
q1[father[v]].pb({d,1,id});
q1[u].pb({d,-1,id});
q2[son[u]].pb({d-1,-1,id});
}q3[z].pb({d,1,id});
}void dfs3(TY now,TY fa){
vector<TY> have;
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==fa||y==son[now])continue;
For(j,id[y],id[y]+siz[y]-1)have.pb(deep[seg[j]]);
}sort(have.begin(),have.end());
sort(q1[now].begin(),q1[now].end(),cmp);
TY tmp=0;
FOR(i,0,q1[now].size()){
while(tmp<have.size()&&have[tmp]<=q1[now][i].d)++tmp;
ans[q1[now][i].id]+=q1[now][i].op*tmp;
}FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==fa)continue;
dfs3(y,now);
}
}void dfs4(TY now,TY fa){
FOR(i,0,q2[now].size()){
if(q2[now][i].d<0)continue;
ans[q2[now][i].id]-=q2[now][i].op*tr.query(deep[now],deep[now]+q2[now][i].d);
}tr.add(deep[now],1);
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==fa)continue;
dfs4(y,now);
}FOR(i,0,q2[now].size()){
if(q2[now][i].d<0)continue;
ans[q2[now][i].id]+=q2[now][i].op*tr.query(deep[now],deep[now]+q2[now][i].d);
}
}void get_siz(TY now,TY fa){
siz[now]=1;maxx[now]=0;
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==fa||vis[y])continue;
get_siz(y,now);
siz[now]+=siz[y];
maxx[now]=max(maxx[now],siz[y]);
}maxx[now]=max(maxx[now],S-siz[now]);
if(maxx[now]<maxx[rt])rt=now;
}void get_ans(TY now,TY deep,TY fa,TY op){
if(op==0){
FOR(i,0,q3[now].size())ans[q3[now][i].id]+=tr.query(0,q3[now][i].d-deep);
}else tr.add(deep,op);
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(y==fa||vis[y])continue;
get_ans(y,deep+1,now,op);
}
}void solve(TY now){
vis[now]=1;
get_siz(now,0);
tr.clear();
tr.add(0,1);
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(vis[y])continue;
get_ans(y,1,now,1);
}FOR(i,0,q3[now].size())ans[q3[now][i].id]+=tr.query(0,q3[now][i].d);
FOR(i,0,e[now].size()){
TY y=e[now][i];
if(vis[y])continue;
get_ans(y,1,now,-1);
get_ans(y,1,now,0);
get_ans(y,1,now,1);
}FOR(i,0,e[now].size()){
TY y=e[now][i];
if(vis[y])continue;
S=siz[y];rt=0;maxx[rt]=1e9;
get_siz(y,now);
solve(rt);
}
}
int main(){
n=qr();
tr.add(0,1);
cout<<tr.query(0,1)<<endl;
FOR(i,1,n){
TY u=qr(),v=qr();
Pb(u,v);
}dfs1(1,0);
dfs2(1,1);
m=qr();
For(i,1,m){
TY u=qr(),v=qr(),d=qr();
query(u,v,d,i);
}dfs3(1,0);
dfs4(1,0);
solve(1);
For(i,1,m)qw(ans[i],'\n');
return 0;
}
/*
6
1 2
2 3
2 4
1 5
4 6
1
2 4 1
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 14ms
memory: 28896kb
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:
1 2945 236 -3382 101 93 639 -411 726 85 1435 127 343 407 130 -1047 1432 -2712 1476 2906 7 1119 -711 -1391 1864 8 40 -3298 -687 126 2630 312 558 736 513 147 1826 685 118 45 -257 1567 47 26 1490 -293 144 -1941 244 34 301 48 119 164 278 -15 -702 48 2988 114 35 2065 388 340 91 4624 1801 7 1357 38 1951 9...
result:
wrong answer 1st numbers differ - expected: '3226', found: '1'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 664ms
memory: 78712kb
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:
1 757 69428 2793 181264 91707 182 32496 199183 6399 15975 11640 119051 236 689 15 9532 41 36592 178936 56 45424 193403 90248 3417 949 68 34133 60471 199861 188090 75088 127 1 6 4 3 3 11 61157 199860 199153 155706 196287 192862 53742 51862 179199 428 196282 199989 3613 26 99007 134461 198159 20382 75...
result:
wrong answer 1st numbers differ - expected: '757', found: '1'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 993ms
memory: 188308kb
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:
1 56 57323 170706 2266 51518 123871 1452 76744 46 7919 69 19 288 26430 15 -9678 351 -129158 53776 6646 48336 166303 59 133144 45343 343 175863 157528 41278 178 21658 194 90 163869 770 17639 -8899 -86276 1243 135725 -49699 16544 13578 33560 27393 25169 46164 206 79 1220 -126096 12408 16724 -63489 294...
result:
wrong answer 1st numbers differ - expected: '78', found: '1'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%