//??https://ac.nowcoder.com/acm/contest/31084/C

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;

typedef long long ll;

const int maxn = 100010;?

int q;

int n;

std::vector<int> son[maxn];

int in[maxn];

int out[maxn];

int tree[maxn];

int num[maxn];

int a[maxn]={0,1 ,4 ,2, 2};

int vis[maxn];

struct node

{

? ? int l,r;

? ? int x;

? ? int id;

}b[maxn];

?int ans[maxn];

int edge[32][2]={

1 ,4,

1 ,2,

2, 3

};

?

void add(int x,int val)

{

? ? while(x<maxn)

? ? {

? ? ? ? tree[x]+=val;

? ? ? ? x+=-x&x;// 上移至父節(jié)點??

? ? }

}

int ask(int x)

{

? ? int res=0;

? ? while(x)

? ? {

? ? ? ? res+=tree[x];

? ? ? ? x-=-x&x;// 子節(jié)點, 如果i=3, 下一個節(jié)點為i=2??

? ? }

? ? return res;

}

int tot=0;

void dfs(int x,int pre)

{

? ? in[x]=++tot;// 以x為根的樹起始頂點編號

? ? num[tot]=x;

? ? for(auto y:son[x])

? ? {

? ? ? ? if(y!=pre)

? ? ? ? {

? ? ? ? ? ? dfs(y,x);

? ? ? ? }

? ? }

? ? out[x]=tot;// 以x為根的樹結(jié)束頂點編號

}

bool cmp(node aa,node bb)

{

? ? return aa.r<bb.r;

}

int main()

{

? ??

? ? gbtb;

n=4;q=3;

? ? //cin>>n>>q;

? ? repd(i,1,n)

? ? {

? ? ? ? //cin>>a[i];

? ? }

? ? int u,v;

? ? repd(i,2,n)

? ? {

? ? ? ? //cin>>u>>v;

u=edge[i-2][0];

v=edge[i-2][1];

? ? ? ? son[u].push_back(v);

? ? ? ? son[v].push_back(u);

? ? }

? ? dfs(1,-1);

? ?repd(i,1,n)cout<<"? num[i]= "<<num[i];

? ?cout<<endl<<"頂點新編號對應(yīng)原來的頂點號碼"<<endl;

? ? repd(i,1,n)

? ? {

? ? ? ? b[i].l=in[i];

? ? ? ? b[i].r=out[i];

? ? ? ? b[i].x=a[i];

? ? ? ? b[i].id=i;// 原來頂點號碼

cout<<"? i= "<<i<<" in[i]="<<in[i]<<"? out[i]="<<out[i]<<endl;

? ? }

? ? sort(b+1,b+1+n,cmp);// 按照b[i].r排序

? ? int p=1;

? ? repd(i,1,n)

? ? { ?

? ? ? ? while(p<=b[i].r)

? ? ? ? {

? ? ? ? ? ? int y=num[p];

//if(i==n)cout<<" vis[a[y]]="<<vis[a[y]]<<" b[i].l="<<b[i].l<<endl;

? ? ? ? ? ? if(vis[a[y]])

? ? ? ? ? ? {?

? ? ? ? ? ? ? ? add(vis[a[y]],-1);// 去除前面相同顏色在tree上面的值， 可能vis[a[y]]<b[i].l

? ? ? ? ? ? ? ? add(p,1);

? ? ? ? ? ? ? ? vis[a[y]]=p;?

? ? ? ? ? ? }else??

? ? ? ? ? ? {

add(p,1);

? ? ? ? ? ? ? ? vis[a[y]]=p;? ? ? ? ? ? ? ??

? ? ? ? ? ? }

? ? ? ? ? ? p++;

? ? ? ? }

cout<<"b[i].id="<<b[i].id<<"? ask(b[i].r)="<< ask(b[i].r)<<"? ?ask(b[i].l-1)="<<ask(b[i].l-1)<<endl;

? ? ? ? ans[b[i].id]=ask(b[i].r)-ask(b[i].l-1);

? ? }

int qu[32]={4,2,1};

? ? while(q--)

? ? {

? ? ? ? int x;

? ? ? ? //cin>>x;

? ? ? ? cout<<qu[q]<<"=qu[q],? "<<ans[qu[q]]<<endl;

? ? }

? ? return 0;

}

?