QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#475325 | #1163. Another Tree Queries Problem | lichenyu_ac | TL | 0ms | 35112kb | C++14 | 4.0kb | 2024-07-13 14:03:22 | 2024-07-13 14:03:23 |
Judging History
answer
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+10,M=N*2;
int head[N],ver[M],nxt[M],tot=1;
void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int n,m,ans;
int d[N],fa[N],s[N],to[N];
int dfn[N],id[N],top[N],cnt;
void dfs1(int x,int father){
fa[x]=father,d[x]=d[father]+1,s[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==father)continue;
dfs1(y,x);
s[x]+=s[y];
if(s[y]>s[to[x]])to[x]=y;
}
}
void dfs2(int x,int t){
dfn[x]=++cnt,id[cnt]=x,top[x]=t;
if(to[x])dfs2(to[x],t);
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(y==fa[x]||y==to[x])continue;
dfs2(y,y);
}
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
x=fa[top[x]];
}
return d[x]<d[y]?x:y;
}
int get_son(int x,int y){
int ret=0;
while(top[x]!=top[y]){
ret=top[x];
x=fa[top[x]];
}
if(x==y)return ret;
else return to[y];
}
#define lc (p<<1)
#define rc (p<<1|1)
#define mid ((L+R)>>1)
ll dat[N<<2],sum_size[N<<2],sum_dep[N<<2],len[N<<2];
struct Tag{
ll a,s,d;
Tag():a(0),s(0),d(0){}
Tag(ll a,ll s,ll d):a(a),s(s),d(d){}
operator bool(){
return a||s||d;
}
void operator+=(const Tag &t){
a+=t.a,s+=t.s,d+=t.d;
}
}tag[N<<2];
void upd(int p){
dat[p]=dat[lc]+dat[rc];
}
void change(int p,const Tag &t){
dat[p]+=t.a*len[p]+t.s*sum_size[p]+t.d*sum_dep[p];
tag[p]+=t;
}
void spread(int p){
if(tag[p]){
change(lc,tag[p]),change(rc,tag[p]);
tag[p]=Tag();
}
}
void build(int p,int L,int R){
len[p]=R-L+1;
if(L==R){
sum_size[p]=s[id[L]];
sum_dep[p]=d[id[L]];
return;
}
build(lc,L,mid),build(rc,mid+1,R);
sum_size[p]=sum_size[lc]+sum_size[rc];
sum_dep[p]=sum_dep[lc]+sum_dep[rc];
}
void change(int p,int L,int R,int l,int r,const Tag &t){
if(l<=L&&R<=r){
change(p,t);
return;
}
spread(p);
if(l<=mid)change(lc,L,mid,l,r,t);
if(r>mid)change(rc,mid+1,R,l,r,t);
upd(p);
}
ll ask(int p,int L,int R,int l,int r){
if(l<=L&&R<=r)return dat[p];
spread(p);
if(r<=mid)return ask(lc,L,mid,l,r);
else if(l>mid)return ask(rc,mid+1,R,l,r);
else return ask(lc,L,mid,l,r)+ask(rc,mid+1,R,l,r);
}
#undef lc
#undef rc
#undef mid
void change_subtree(int x,int k){
change(1,1,n,dfn[x],dfn[x]+s[x]-1,Tag(0,k,0));
k*=s[x],ans+=k;
for(x=fa[x];x;x=fa[top[x]])change(1,1,n,dfn[top[x]],dfn[x],Tag(k,0,0));
}
void change_chain(int x,int y){
int p=LCA(x,y),dx=d[x]+1,dy=d[y]+1,dist=dx+dy-1-d[p]*2;
ans+=dist;
while(top[x]!=top[p]){
change(1,1,n,dfn[top[x]],dfn[x],Tag(dx,0,-1));
}
if(x!=p)change(1,1,n,dfn[p]+1,dfn[x],Tag(dx,0,-1));
while(top[y]!=top[p]){
change(1,1,n,dfn[top[y]],dfn[y],Tag(dy,0,-1));
}
if(y!=p)change(1,1,n,dfn[p]+1,dfn[y],Tag(dy,0,-1));
for(;p;p=fa[top[p]])change(1,1,n,dfn[top[p]],dfn[p],Tag(dist,0,0));
}
ll ask(int x){
ll ret=d[x]*ans+dat[1];
while(x){
ret-=2*ask(1,1,n,dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
return ret;
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs1(1,0),dfs2(1,1),build(1,1,n);
scanf("%d",&m);
while(m--){
int op,x,y;
scanf("%d%d",&op,&x);
if(op==1){
scanf("%d",&y);
if(x==y)change_subtree(1,1);
else if(dfn[y]<dfn[x]&&dfn[x]<dfn[y]+s[y]){
change_subtree(1,1);
change_subtree(get_son(x,y),-1);
}else change_subtree(y,1);
}else if(op==2){
scanf("%d",&y);
change_chain(x,y);
}else printf("%lld\n",ask(x));
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 35112kb
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
Time Limit Exceeded
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 ...