dsu on tree TLE on #9 求调
查看原帖
dsu on tree TLE on #9 求调
508032
int08楼主2024/8/28 20:42

不知道为啥,是我写假了吗

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
using namespace std;
#define N 214514
int sz[N],d[N],ans[N],a[N];
pair<int,int> son[N];
vector<int> e[N];
vector<pair<int,int> > q[N];
set<int> s[N];
string st[N];
map<string,int> ma;
void dfs1(int u)
{
	sz[u]=1;
	for(auto v:e[u]) d[v]=d[u]+1,dfs1(v),sz[u]+=sz[v],son[u]=max(son[u],{sz[v],v});
}
void dfs3(int u)
{
	s[d[u]].insert(a[u]);
	for(auto v:e[u]) dfs3(v);
}
void dfs2(int u)
{
	for(auto v:e[u]) if(v!=son[u].second)
	{
		dfs2(v);
		for(int i=d[v];s[i].size();i++) s[i].clear();
	}
	if(son[u].second) dfs2(son[u].second);
	s[d[u]].insert({a[u]});
	for(auto v:e[u]) if(v!=son[u].second) dfs3(u);
	for(auto x:q[u])
		ans[x.second]=s[d[u]+x.first].size();
}
int n,m,i,f,u,x,mcn;
int main()
{
	cin.tie(0)->sync_with_stdio(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++) cin>>st[i]>>f,ma[st[i]]=0,e[f].push_back(i);
	for(auto &x:ma) x.second=++mcn;
	for(i=1;i<=n;i++) a[i]=ma[st[i]];
	dfs1(0);
	cin>>m;
	for(i=1;i<=m;i++)
	{
		cin>>u>>x;
		q[u].push_back({x,i});
	}
	dfs2(0);
	for(i=1;i<=m;i++) cout<<ans[i]<<endl;
}
2024/8/28 20:42
加载中...