#include #include #include using namespace std; #include #include template struct lazysegtree{ functioncalcfn,lazycalcfn; functionupdatefn; int n; T defvalue,lazydefvalue; vectordat,lazy; vectorlazyflag; lazysegtree(int n_=0,T defvalue_=0, functioncalcfn_=[](T a,T b){return a+b;}, functionlazycalcfn_=[](T a,T b){return a+b;}, functionupdatefn_=[](T a,T b,unsigned int width){return a+b*width;}, T lazydefvalue_=0 ):defvalue(defvalue_),lazydefvalue(lazydefvalue_), calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_) { n=1; while(n&v) { for(int i=0;i=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]); } void eval(int i,int l,int r) { if(lazyflag[i]) { dat[i]=updatefn(dat[i],lazy[i],r-l); if(r-l>1) { lazy[2*i+1]=lazycalcfn(lazy[2*i+1],lazy[i]); lazy[2*i+2]=lazycalcfn(lazy[2*i+2],lazy[i]); lazyflag[2*i+1]=lazyflag[2*i+2]=true; } lazy[i]=lazydefvalue; lazyflag[i]=false; } } void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return; else if(a<=l&&r<=b) { lazy[k]=lazycalcfn(lazy[k],x); lazyflag[k]=true; eval(k,l,r); } else { update(a,b,x,2*k+1,l,(l+r)/2); update(a,b,x,2*k+2,(l+r)/2,r); dat[k]=calcfn(dat[2*k+1],dat[2*k+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return defvalue; else if(a<=l&&r<=b)return dat[k]; else return calcfn( query(a,b,2*k+1,l,(l+r)/2), query(a,b,2*k+2,(l+r)/2,r) ); } }; //Disjoint Sparse Table #include #include template struct DST{ functioncalcfn; int n; vector >dat; DST(const vector&v={}, functioncalcfn_=[](T a,T b){return a(n)); for(int j=i;jn)r=n; r--; if(l==r)return dat[0][l]; int k=31-__builtin_clz(l^r); return calcfn(dat[k][l],dat[k][r]); } }; int N; vectorG[1<<17]; int Lc[1<<17],Rc[1<<17]; int p[1<<17]; vectorA; int Ainv[1<<17]; main() { cin>>N; for(int i=1;i>u>>v; G[u].push_back(v); G[v].push_back(u); } for(int i=0;iPP; PP.push(0); A.push_back(0); while(!PP.empty()) { int u=PP.front();PP.pop(); for(int v:G[u]) { if(v==p[u])continue; if(Lc[u]<0)Lc[u]=A.size(); A.push_back(v); Rc[u]=A.size(); p[v]=u; PP.push(v); } } for(int i=0;iB(N); for(int i=0;i>B[Ainv[i]]; lazysegtreeP(N,0,[](long a,long b){return a+b;}, [](long a,long b){return b;}, [](long a,long b,unsigned int w){return b*w;}); vectorLc2(N),Rc2(N); for(int i=0;iP2(Lc2,[](int a,int b){return a==-1?b:b==-1?a:aP3(Rc2,[](int a,int b){return a>Q; for(;Q--;) { int x;cin>>x; long ans=0; if(Lc[x]>=0) { int L=Lc[x],R=Rc[x]; ans+=P.query(L,R); P.update(L,R,0); int L2=P2.query(L,R); int R2=P3.query(L,R); if(L2>=0) { ans+=P.query(L2,R2); P.update(L2,R2,0); } } if(p[x]>=0) { int u=p[x]; ans+=P.query(Lc[u],Rc[u]); P.update(Lc[u],Rc[u],0); if(p[u]>=0) { int v=p[u]; ans+=P.query(Ainv[v],Ainv[v]+1); P.update(Ainv[v],Ainv[v]+1,0); } ans+=P.query(Ainv[u],Ainv[u]+1); P.update(Ainv[u],Ainv[u]+1,0); } else { ans+=P.query(Ainv[x],Ainv[x]+1); P.update(Ainv[x],Ainv[x]+1,0); } cout<