QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#702904 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | FLY | 0 | 794ms | 180040kb | C++14 | 5.7kb | 2024-11-02 16:46:37 | 2024-11-02 16:46:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define gc getchar
#define pb push_back
#define abs_(x) max(x,-(x))
#define tomin(x,y) x=min(x,y)
#define tomax(x,y) x=max(x,y)
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define dFor(i,a,b) for(int i=(a);i>=(b);i--)
#define all(x) x.begin(),x.end()
const int N=2e5+5;
int read()
{
int x=0; int y=1; char c=gc();
for(;!isdigit(c);c=getchar()) if(c=='-') y=0;
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return y?x:-x;
}
int n,Q;
vector<int> e[N];
int ans[N];
int fa[N],d[N],sz[N],son[N],dfn[N],idfn[N],ed[N],dct,top[N];
int bz[20][N],lg[N];
void dfs0(int u)
{
d[u]=d[fa[u]]+1;
sz[u]=1;
son[u]=0;
for(int v:e[u]) if(v^fa[u])
{
fa[v]=u;
dfs0(v);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs1(int u,int tp)
{
top[u]=tp;
dfn[u]=++dct;
idfn[dfn[u]]=u;
bz[0][dct]=dfn[fa[u]];
if(son[u]) dfs1(son[u],tp);
for(int v:e[u]) if((v^fa[u])&&(v^son[u]))
{
dfs1(v,v);
}
ed[u]=dct;
}
int get_mn(int l,int r)
{
int t=lg[r-l+1];
return min(bz[t][l],bz[t][r-(1<<t)+1]);
}
int lca(int u,int v)
{
if(u==v) return u;
u=dfn[u],v=dfn[v];
if(u>v) swap(u,v);
return idfn[get_mn(u+1,v)];
}
int dis(int u,int v)
{
return d[u]+d[v]-2*d[lca(u,v)];
}
int Fa[N],Sz[N],Rt,n2;
bool vs[N];
vector<int> d1[N],d2[N];
int tsz[N],mx[N];
void dfs2(vector<int> &x,int u,int fa,int s)
{
// cout<<u<<" ";
// cout<<" "<<s<<" "<<u<<endl;
// cout<<u<<endl;
x[dis(u,s)]++;
for(int v:e[u]) if((v^fa)&&!vs[v]) dfs2(x,v,u,s);
}
int get_sz(int u,int fa)
{
// cout<<u<<endl;
int s=1;
for(int v:e[u]) if((v^fa)&&!vs[v]) s+=get_sz(v,u);
return s;
}
void get_rt(int u,int fa)
{
// cout<<u<<endl;
tsz[u]=1; mx[u]=0;
for(int v:e[u]) if((v^fa)&&!vs[v])
{
get_rt(v,u);
tsz[u]+=tsz[v];
tomax(mx[u],tsz[v]);
}
tomax(mx[u],n2-tsz[u]);
if(mx[u]*2<=n2) Rt=u;
}
void Divide(int u)
{
// cout<<u<<endl;
vs[u]=1;
d1[u].resize(Sz[u]+3,0);
d2[u].resize(Sz[u]+3,0);
dfs2(d1[u],u,0,u);
// puts("");
if(u^1) dfs2(d2[u],u,0,Fa[u]);
// puts("");
for(int i=1;i<d1[u].size();i++) d1[u][i]+=d1[u][i-1];
for(int i=1;i<d2[u].size();i++) d2[u][i]+=d2[u][i-1];
// for(int i=0;i<d1[u].size();i++) cout<<d2[u][i]<<" ";
// puts("");
// puts("");
for(int v:e[u]) if(!vs[v])
{
n2=get_sz(v,u);
get_rt(v,u);
Fa[Rt]=u;
Sz[Rt]=n2;
Divide(Rt);
}
}
int query1(int u,int d)
{
int s=0;
for(int v=u;v;v=Fa[v])
{
int t=dis(v,u);
if(t<=d)
{
int tt=(int)d1[v].size()-1;
s+=d1[v][min(tt,d-t)];
// cout<<u<<" "<<v<<" "<<d<<" "<<t<<" "<<d1[v][d-t]<<","<<d2[v][d-t]<<endl;
if(v!=1&&dis(u,Fa[v])<=d) s-=d2[v][min(tt,d-dis(u,Fa[v]))];
}
}
return s;
}
void pre1()
{
For(i,2,n) lg[i]=lg[i>>1]+1;
dfs0(1);
dfs1(1,1);
For(i,1,lg[n])
{
For(j,1,n-(1<<i)+1) bz[i][j]=min(bz[i-1][j],bz[i-1][j+(1<<i-1)]);
}
Sz[1]=n;
Divide(1);
// For(i,1,n)
// {
// For(j,1,n) cout<<dis(i,j)<<" ";
// puts("");
// }
}
struct _N
{
int id,d,x;
};
vector<_N> g1[N],g2[N];
void solve(int id,int u,int d,int x)
{
g1[u].pb((_N){id,d,x});
if(d)
{
g2[son[u]].pb((_N){id,d-1,x});
for(int v=top[u];v^1;v=top[fa[v]])
{
g2[v].pb((_N){id,d-1,-x});
g2[son[fa[v]]].pb((_N){id,d-1,x});
}
}
}
namespace B
{
int c[N];
void cls() { memset(c,0,sizeof(c)); }
#define lb(x) x&-x
void add(int x,int y)
{
x++;
for(int i=x;i<=n+2;i+=lb(i)) c[i]+=y;
}
void cls(int x)
{
x++;
for(int i=x;i<=n+2;i+=lb(i)) c[i]=0;
}
int get(int x)
{
x++;
tomin(x,n+2);
int s=0;
for(int i=x;i;i-=lb(i)) s+=c[i];
return s;
}
int get(int l,int r) { return get(r)-get(l-1); }
#undef lb
}
void dfs4(int u,int d,int x)
{
B::add(d,x);
for(int v:e[u]) if(v^fa[u]) dfs4(v,d+1,x);
}
void dfs3(int u)
{
B::add(0,1);
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs4(v,1,1);
for(auto t:g1[u])
{
int s=B::get(t.d)*t.x;
// cout<<" "<<t.id<<" "<<u<<" "<<t.d<<" "<<s<<endl;
ans[t.id]+=s;
}
for(int v:e[u])
{
if((v^fa[u])) dfs3(v);
}
B::add(0,-1);
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs4(v,1,-1);
}
void dfs6(int u,int x)
{
B::add(d[u],x);
for(int v:e[u]) if(v^fa[u]) dfs6(v,x);
}
void dfs5(int u,bool cs)
{
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs5(v,1);
if(son[u]) dfs5(son[u],0);
B::add(d[u],1);
for(int v:e[u]) if((v^fa[u])&&(v^son[u])) dfs6(v,1);
for(auto t:g2[u])
{
int s=B::get(d[u],d[u]+t.d)*t.x;
// For(i,0,2) cout<<B::get(i)<<" "; puts("");
// cout<<" "<<t.id<<" "<<u<<" "<<t.d<<" "<<s<<endl;
ans[t.id]+=s;
}
if(cs)
{
For(k,dfn[u],ed[u]) B::cls(d[idfn[k]]);
}
}
void work1()
{
dfs3(1);
dfs5(1,1);
}
void Cls()
{
For(u,1,n) e[u].clear();
dct=0;
memset(ans,0,Q+2<<2);
For(u,1,n) d1[u].clear();
For(u,1,n) d2[u].clear();
memset(vs,0,n+2);
For(u,1,n) g1[u].clear();
For(u,1,n) g2[u].clear();
}
void work()
{
n=read();
For(i,1,n-1)
{
int u=read(),v=read();
e[u].pb(v);
e[v].pb(u);
}
pre1();
Q=read();
For(i,1,Q)
{
int u=read(),v=read(),d=read();
int lc=lca(u,v);
// cout<<lc<<endl;
solve(i,u,d,1);
solve(i,v,d,1);
solve(i,lc,d,-2);
ans[i]+=query1(lc,d);
// cout<<" "<<query1(u,d)<<" "<<query1(v,d)<<endl;
}
work1();
For(i,1,Q) printf("%d\n",ans[i]);
Cls();
}
signed main()
{
// freopen("ex_color.in","r",stdin);
// freopen("color.in","r",stdin);
// freopen("color.out","w",stdout);
// freopen("D.in","r",stdin);
// freopen("D.out","w",stdout);
int T=1;
while(T--) work();
return 0;
}
/*
5
1 2
1 3
2 4
2 5
5
1 2 0
1 2 1
1 2 2
1 2 3
4 3 1
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 14ms
memory: 45884kb
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:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 49...
result:
wrong answer 757th numbers differ - expected: '120', found: '121'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 794ms
memory: 180040kb
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:
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 7518...
result:
wrong answer 1057th numbers differ - expected: '282', found: '283'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 771ms
memory: 156396kb
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:
78 107329 190250 5672 110415 199160 3826 96672 75 13429 149 58 704 199639 25 190454 489 198350 197627 10273 172193 192719 99 191654 80328 481 195140 170809 120515 290 199616 719 142 195166 2607 20737 135444 199768 2433 164666 180527 198261 14511 53672 69060 185790 110874 639 131 2130 188357 150164 2...
result:
wrong answer 5292nd numbers differ - expected: '371', found: '372'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%