之前的模板错了一个地方。。。调的时候怎么也不行。。。

讯享网

#include<iostream> #include<cstdio> #define MAXN  #define LL long long using namespace std; //use of main LL n,m; //use of pre_star struct edge { LL next,to; edge(){next=to=0;} }len[MAXN*2]; LL fst[MAXN*2]={0}; LL num=0; inline void add(LL u,LL v) {len[++num].next=fst[u],len[num].to=v,fst[u]=num;} //use of SP LL fa[MAXN]={0},son[MAXN]={0}; LL top[MAXN]={0},size[MAXN]={0},dep[MAXN]={0}; LL po[MAXN]={0}; LL cnt=0; //use of tree struct tree { LL sum,add; tree(){sum=add=0;} }use[MAXN*4]; inline LL lc(LL x){return x<<1;} inline LL rc(LL x){return x<<1|1;} inline void swap(LL &a,LL &b){LL t=a;a=b;b=t;} void dfs_1(LL x,LL deep) { dep[x]=deep; size[x]=1,son[x]=0; for(LL i=fst[x];i;i=len[i].next) if(len[i].to!=fa[x]) { fa[len[i].to]=x; dfs_1(len[i].to,deep+1); size[x]+=size[len[i].to]; if(size[len[i].to]>size[son[x]]) son[x]=len[i].to; } } void dfs_2(LL x,LL pre) { top[x]=pre,po[x]=++cnt; if(son[x]!=0)dfs_2(son[x],pre); for(LL i=fst[x];i;i=len[i].next) if(len[i].to!=fa[x]&&len[i].to!=son[x]) dfs_2(len[i].to,len[i].to); } inline void up(LL x) { use[x].sum=use[lc(x)].sum+use[rc(x)].sum; } inline void down(LL x,LL op,LL ed) { if(use[x].add!=0) { LL l=lc(x),r=rc(x); LL mid=(op+ed)>>1; use[l].sum+=use[x].add*(mid-op+1); use[r].sum+=use[x].add*(ed-mid); use[l].add+=use[x].add; use[r].add+=use[x].add; use[x].add=0; } } void update(LL x,LL l,LL r,LL op,LL ed) { if(op<=l&&r<=ed) { use[x].sum+=(r-l+1); use[x].add++; return ; } down(x,l,r); LL mid=(l+r)>>1; if(ed<=mid)update(lc(x),l,mid,op,ed); else if(op>mid)update(rc(x),mid+1,r,op,ed); else update(lc(x),l,mid,op,ed),update(rc(x),mid+1,r,op,ed); up(x); } LL query(LL x,LL l,LL r,LL op,LL ed) { if(op<=l&&r<=ed) return use[x].sum; down(x,l,r); LL mid=(l+r)>>1; LL ans=0; if(ed<=mid)ans+=query(lc(x),l,mid,op,ed); else if(op>mid)ans+=query(rc(x),mid+1,r,op,ed); else ans+=query(lc(x),l,mid,op,ed)+query(rc(x),mid+1,r,op,ed); return ans; } void find_sum(LL a,LL b) { LL t1=top[a],t2=top[b]; while(t1!=t2) { if(dep[t1]<dep[t2]){swap(t1,t2),swap(a,b);} update(1,1,n,po[t1],po[a]); a=fa[t1],t1=top[a]; } if(dep[a]<dep[b])update(1,1,n,po[a],po[b]); else update(1,1,n,po[b],po[a]); } LL ans_sum(LL a,LL b) { int t1=top[a],t2=top[b]; LL ans=0; while(t1!=t2) { if(dep[t1]<dep[t2]){swap(a,b),swap(t1,t2);} ans+=query(1,1,n,po[t1],po[a]); a=fa[t1],t1=top[a]; } if(dep[a]<dep[b])ans+=query(1,1,n,po[a],po[b]); else ans+=query(1,1,n,po[b],po[a]); return ans; } int main() { scanf("%I64d",&n); LL t1,t2; for(int i=1;i<n;i++) { scanf("%I64d%I64d",&t1,&t2); add(t1,t2),add(t2,t1); } dfs_1(1,1); dfs_2(1,1); //* scanf("%d",&m); int k=0; for(int i=1;i<=m;i++) { scanf("%d%I64d%I64d",&k,&t1,&t2); if(k==1) { find_sum(t1,t2); } else if(k==2) { printf("%lld\n",ans_sum(t1,t2)); } } //*/ //while(1); return 0; //1 2 5 3 4 /* 1(2) 2(2) 4(1) 3(1) 5(1) */ }