AcWing 5723. 文件夹合并csp33(5)四十分!
原题链接
困难
作者:
YAX_AC
,
2024-11-20 22:45:13
,
所有人可见
,
阅读 5
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 500010;
int n;
LL d[N];
int fa[N];
vector<int> e[N];
void solve()
{
int Q;
cin>>n>>Q;
for(int i = 2; i<=n; i++)
{
int f;cin>>f;
e[f].push_back(i);
fa[i] = f;
}
for(int i = 1; i<=n; i++) cin>>d[i];
while(Q--)
{
int op,x; cin>>op>>x;
if(op==1)
{
vector<int> son;
for(int j:e[x]) son.push_back(j);
for(int j:son) d[x] += d[j];
e[x].clear();//清空所有儿子
//将儿子的子节点,连到当前要合并的节点x上
for(int j:son)//儿子
for(int k:e[j])//儿子的子节点
e[x].push_back(k),fa[k] = x;//还要记录儿子的子节点的父节点,变成了当前节点x
cout<<(int)e[x].size()<<' '<<d[x]<<endl;
}
else//操作2:询问路径(会tle)
{
int now = x,path = 1;//路径是询问从根结点1到x结点一共有多少结点,路径+1=结点数量
while(now != 1)
{
path++;
now = fa[now];
}
cout<<path<<endl;
}
}
}
int main()
{
solve();
return 0;
}