#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; template struct LazySegmentTree{ using F=function; using G=function; using H=function; int sz; vector data; vector lazy; const F f; const G g; const H h; const Monoid e1; const OperatorMonoid e0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){ sz=1; while(sz v){ for(int i=0; i=0; i--) data[i]=f(data[2*i+1], data[2*i+2]); } void eval(int k, int l, int r){ if(lazy[k]!=e0){ data[k]=g(data[k], lazy[k], r-l); if(k> g; ll a[100010]; int ind[100010]; int par[100010]; int main() { int n; cin>>n; g.resize(n); for(int i=0; i>u>>v; g[u].push_back(v); g[v].push_back(u); } for(int i=0; i>a[i]; queue que; que.push(0); par[0]=-1; int c=0; while(!que.empty()){ int x=que.front(); que.pop(); ind[x]=c; c++; for(auto y:g[x]){ if(y!=par[x]){ que.push(y); par[y]=x; } } } for(int i=0; i va(n); for(int i=0; i seg(n, f, g1, h, 0, INF); seg.build(va); int l2[100010], r2[100010]; for(int i=0; i>Q; for(int i=0; i>x; ll s=seg[ind[x]]; seg.update(ind[x], ind[x]+1, 0); if(par[x]!=-1){ int p=par[x]; s+=seg[ind[p]]; seg.update(ind[p], ind[p]+1, 0); if(par[p]!=-1){ s+=seg[ind[par[p]]]; seg.update(ind[par[p]], ind[par[p]]+1, 0); } int l=ind[g[p][0]], r=ind[g[p].back()]; s+=seg.find(l, r+1); seg.update(l, r+1, 0); } if(!g[x].empty()){ int l=ind[g[x][0]], r=ind[g[x].back()]; s+=seg.find(l, r+1); seg.update(l, r+1, 0); if(l2[x]!=-1){ s+=seg.find(ind[l2[x]], ind[r2[x]]+1); seg.update(ind[l2[x]], ind[r2[x]]+1, 0); } } cout<