A：構造一組數據
顯然第一個數只能比較一次，構造前兩個數最大，而且相等即可
B：求出總和，如果是n的倍數，說明總能構造出所有數相等，如果 不是n的倍數，那麼總可以利用一個數，將其它n-1個數構造 相等
C：卡了好久的題。注意K的范圍(n+1)*n/2，明顯是1+2……n
將數列倒序，a0,a1,a2,a3 (ai>ai+1)
考慮只取一個數，那麼有n種可能，而且這n種互不相同
考慮取兩個數，其中a0必取，從剩下的n-1個數中取一個，有n-1種可能，這n-1種互不相同 ，另外考慮與前n種比較，前n種的最大值顯然是a0,而後n-1種a0+ai>a0，所以不相同
同理取三個數，取四個數，取n個數
對於取i個數，總是前i-1大的數必取。
所以總共的情況為n+n-1+n-2……+2+1
D：直接暴力，用set就行了
E：遞歸離線一直RE，哭
在線也可以，遍歷整棵樹，標號，對於結點u，所有後代的標號總在(left[u],right[r])區間內。
對於一個查詢，可以通過二分定位這層的區間
可能有重復查詢，map記錄一下，不然會T
[cpp]
vector<int>e[N];
map<pair<int,int>,int>ans;
int n;
char str[105];
string name[N];
int Left[N],Right[N];
int depth[N],idx=0;
int max_depth=-1;
vector<int>dep[N];
void dfs(int u,int h)
{
max_depth=max(max_depth,h);
depth[u]=h;
dep[h].pb(u);
Left[u]=idx++;
for(int i=0;i<e[u].size();i++) dfs(e[u][i],h+1);
Right[u]=idx++;
}
int query(int u,int k,int l,int r)
{
int h=depth[u]+k;
if(h>max_depth) return 0;
if(dep[h].empty()) return 0;
if(ans.find(mp(u,k))!=ans.end()) return ans[mp(u,k)];
int low=0,high=dep[h].size()-1,mid,L=N,R=-1;
while(low<=high){
mid=(low+high)>>1;
if(Left[dep[h][mid]]>l){
high=mid-1;
L=mid;
}
else low=mid+1;
}
low=0,high=dep[h].size()-1;
while(low<=high){
mid=(low+high)>>1;
if(Left[dep[h][mid]]<r){
low=mid+1;
R=mid;
}
else high=mid-1;
}
set<string>s;
while(L<=R) s.insert(name[dep[h][L]]),L++;
return ans[mp(u,k)]=s.size();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%s%d",str,&k);
name[i]=string(str,strlen(str));
e[k].pb(i);
}
dfs(0,0);
int q;
scanf("%d",&q);
while(q--)
{
int u,k;
scanf("%d%d",&u,&k);
printf("%d\n",query(u,k,Left[u],Right[u]));
}
return 0;
}
vector<int>e[N];
map<pair<int,int>,int>ans;
int n;
char str[105];
string name[N];
int Left[N],Right[N];
int depth[N],idx=0;
int max_depth=-1;
vector<int>dep[N];
void dfs(int u,int h)
{
max_depth=max(max_depth,h);
depth[u]=h;
dep[h].pb(u);
Left[u]=idx++;
for(int i=0;i<e[u].size();i++) dfs(e[u][i],h+1);
Right[u]=idx++;
}
int query(int u,int k,int l,int r)
{
int h=depth[u]+k;
if(h>max_depth) return 0;
if(dep[h].empty()) return 0;
if(ans.find(mp(u,k))!=ans.end()) return ans[mp(u,k)];
int low=0,high=dep[h].size()-1,mid,L=N,R=-1;
while(low<=high){
mid=(low+high)>>1;
if(Left[dep[h][mid]]>l){
high=mid-1;
L=mid;
}
else low=mid+1;
}
low=0,high=dep[h].size()-1;
while(low<=high){
mid=(low+high)>>1;
if(Left[dep[h][mid]]<r){
low=mid+1;
R=mid;
}
else high=mid-1;
}
set<string>s;
while(L<=R) s.insert(name[dep[h][L]]),L++;
return ans[mp(u,k)]=s.size();
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int k;
scanf("%s%d",str,&k);
name[i]=string(str,strlen(str));
e[k].pb(i);
}
dfs(0,0);
int q;
scanf("%d",&q);
while(q--)
{
int u,k;
scanf("%d%d",&u,&k);
printf("%d\n",query(u,k,Left[u],Right[u]));
}
return 0;
}
