#include using namespace std; #define TRACE #ifdef TRACE #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__) template void __f(const char* name, Arg1&& arg1){ cerr << name << " : " << arg1 << std::endl; } template void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); } #else #define trace(...) #endif #define si(x) scanf("%d",&x) #define sll(x) scanf("%lld",&x) #define pi(x) printf("%d\n",x) #define F first #define S second #define PB push_back #define MP make_pair #define LET(x,a) __typeof(a) x(a) #define TR(v,it) for( LET(it,v.begin()) ; it != v.end(); it++) typedef long long LL; typedef pair PII; typedef vector VI; typedef vector VPII; const int mod = 1000000007; inline void add(int &x, int y){x+=y; if(x>=mod)x-=mod; if(x<0)x+=mod;} inline int mul(int x, int y){ return ((LL)x * y)%mod;} int gcd(int a, int b){ if(b)return gcd(b,a%b); return a;} int power(int a ,int p){int ret = 1; while(p){if(p&1)ret=mul(ret,a); a=mul(a,a); p/=2;}return ret;} int phi(int n){ int ret=n; int i = 2; if(n%i==0){ ret-=ret/i; while(n%i==0)n/=i;} for(i=3; i*i<=n; i++)if(n%i==0){ ret-=ret/i; while(n%i==0)n/=i;} if(n>1)ret-=ret/n;return ret; } const int N = 200000; const int LG = 19; int tim; int depth[N+1], parent[LG][N+1], out[N+1]; int in[N]; VI edge[N]; int n; void dfs(int x, int d, int p) { in[x] = ++tim; parent[0][tim] = in[p]; depth[tim] = d; for(auto y : edge[x]) if(y != p) dfs(y,d+1,x); out[in[x]] = tim; } int lca(int x, int y) { if(depth[x] < depth[y])swap(x,y); int d = depth[x] - depth[y]; int l =0; while(d>0){ if(d&1) x = parent[l][x]; d/=2; l++; } if(x==y)return x; for(int l = LG-1; l>=0; l--){ if(parent[l][x]==parent[l][y])continue; x = parent[l][x]; y = parent[l][y]; } return parent[0][x]; } int BT1[N+1], BT2[N+1]; void update(int BT[], int x, int val) { while(x<=n){BT[x] += val; x += (x & (-x));} } int query(int BT[], int id) { int ret = 0; while(id>0) { ret += BT[id]; id &= (id-1); } return ret; } int query(int BT[], int l, int r) { return query(BT,r) - query(BT,l-1); } void input() { si(n); assert(n>0); for(int i =0; i