QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470499#1163. Another Tree Queries ProblemmaojunWA 101ms35132kbC++232.9kb2024-07-10 14:32:352024-07-10 14:32:36

Judging History

你现在查看的是最新测评结果

  • [2024-07-10 14:32:36]
  • 评测
  • 测评结果:WA
  • 用时:101ms
  • 内存:35132kb
  • [2024-07-10 14:32:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e5+5;
int n,q;
const int E=N<<1;
int tot=0,head[N],to[E],nxt[E];
inline void Add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
#define go(chk) for(int i=head[u];i;i=nxt[i])if(int v=to[i];chk)

int dfc=0,fa[N],dep[N],siz[N],son[N],top[N],dfn[N],id[N];
void dfs1(int u,int fath){fa[u]=fath;dep[u]=dep[fath]+1;siz[u]=1;go(v^fath){dfs1(v,u);siz[u]+=siz[v];siz[v]>siz[son[u]]&&(son[u]=v);}}
void dfs2(int u,int tp){top[u]=tp;id[dfn[u]=++dfc]=u;if(!son[u])return;dfs2(son[u],tp);go(v^fa[u]&&v^son[u])dfs2(v,v);}
inline int LCA(int u,int v){for(;top[u]^top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);return dep[u]<dep[v]?u:v;}
inline int gson(int u,int v){int lst;for(;top[u]^top[v];u=fa[lst=top[u]]);return u==v?lst:son[v];}
const int S=N<<2;
ll B[S],SZ[S],DP[S];int ln[S];
struct TAG{
	ll a,s,d;TAG():a(0),s(0),d(0){}TAG(int a,int s,int d):a(a),s(s),d(d){}
	operator bool(){return a||s||d;}
	void operator+=(const TAG&b){a+=b.a;s+=b.s;d+=b.d;}
}tg[S];
#define ls p<<1
#define rs p<<1|1
#define mid (l+r>>1)
#define Ls ls,l,mid
#define Rs rs,mid+1,r
#define all 1,1,n
inline void pu(int p){B[p]=B[ls]+B[rs];}
inline void chg(int p,TAG k){B[p]+=k.a*ln[p]+k.s*SZ[p]+k.d*DP[p];tg[p]+=k;}
inline void pd(int p){if(tg[p]){chg(ls,tg[p]);chg(rs,tg[p]);tg[p]=TAG();}}
void bld(int p,int l,int r){ln[p]=r-l+1;if(l==r){SZ[p]=siz[id[l]];DP[p]=dep[id[l]];return;}bld(Ls);bld(Rs);SZ[p]=SZ[ls]+SZ[rs];DP[p]=DP[ls]+DP[rs];}
void U(int p,int l,int r,int L,int R,TAG k){if(L<=l&&r<=R)return chg(p,k);pd(p);if(L<=mid)U(Ls,L,R,k);if(R>mid)U(Rs,L,R,k);pu(p);}
ll Q(int p,int l,int r,int L,int R){if(L<=l&&r<=R)return B[p];pd(p);return L>mid?Q(Rs,L,R):R<=mid?Q(Ls,L,R):Q(Ls,L,R)+Q(Rs,L,R);}
ll A=0;
inline void Utree(int u,int k){
	A+=siz[u];
	U(all,dfn[u],dfn[u]+siz[u]-1,TAG(0,k,0));
	k*=siz[u];
	for(u=fa[u];u;u=fa[top[u]])U(all,dfn[top[u]],dfn[u],TAG(k,0,0));
}
inline void Upath(int u,int v){
	int l=LCA(u,v),du=dep[u]+1,dv=dep[v]+1,d=du+dv-1-dep[l]*2;
	A+=d;
	for(;top[u]^top[l];u=fa[top[u]])U(all,dfn[top[u]],dfn[u],TAG(du,0,-1));if(u^l)U(all,dfn[l]+1,dfn[u],TAG(du,0,-1));
	for(;top[v]^top[l];v=fa[top[v]])U(all,dfn[top[v]],dfn[v],TAG(dv,0,-1));if(v^l)U(all,dfn[l]+1,dfn[v],TAG(dv,0,-1));
	for(;l;l=fa[top[l]])U(all,dfn[top[l]],dfn[l],TAG(d,0,0));
}
inline ll Qall(int u){
	ll res=dep[u]*A+B[1];
	for(;u;u=fa[top[u]])res-=2*Q(all,dfn[top[u]],dfn[u]);
	return res;
}
int main(){
	scanf("%d",&n);
	for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);Add(u,v);Add(v,u);}
	dfs1(1,0);dfs2(1,1);bld(all);
	scanf("%d",&q);
	for(int o,u,v;q--;){
		scanf("%d%d",&o,&u);
		if(o==1){
			scanf("%d",&v);
			if(u==v)Utree(1,1);
			else if(dfn[v]<dfn[u]&&dfn[u]<dfn[v]+siz[v]){Utree(1,1);Utree(gson(u,v),-1);}
			else Utree(v,1);
		}else if(o==2){scanf("%d",&v);Upath(u,v);}
		else printf("%lld\n",Qall(u));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 35132kb

input:

5
4 2
2 5
1 5
1 3
5
2 2 4
3 4
2 1 5
2 5 5
3 2

output:

1
5

result:

ok 2 number(s): "1 5"

Test #2:

score: -100
Wrong Answer
time: 101ms
memory: 34576kb

input:

200
171 114
50 183
28 68
67 152
139 125
67 55
50 98
106 71
46 42
157 165
42 49
113 12
81 145
105 13
38 96
34 156
24 17
21 191
135 54
174 116
177 157
123 71
95 130
135 193
150 129
25 190
96 93
188 173
90 160
86 187
20 132
199 75
59 195
189 24
40 68
163 83
25 13
73 33
59 50
154 19
146 21
151 67
89 69
...

output:

826
908
813
1785
2288
1320
3038
2403
4809
3933
4123
3791
5819
4597
6632
7523
4562
8021
7393
9809
7647
6024
11272
7024
12979
14995
9349
9115
8493
11255
18524
22790
16363
18080
11343
14599
12101
19050
12424
18951
25862
22196
26160
20705
14874
23884
13961
20742
14119
26710
19906
31390
20416
34990
18509...

result:

wrong answer 29th numbers differ - expected: '8437', found: '8493'