题意就丢个链接吧:https://loj.ac/problem/6175
看完题之后，我的第一反应就是跑拓扑图啊
因为我比较无脑，然后就开始打了
WA了。。。。
然后想啊想啊，最后喵了眼题解，发现了一句重要的情况
假设有这样一种情况：
其K：4 10 2 2 1 1 1 1
这样的话，我们肯定先选8作为起点，染色到5.那么暴力去想的话继续以4为起点，染色到4，再以3为起点，染色到3..............依次类推的话，其结果就是5.
但是显然我们的正解答案是2.
这样就很尴尬啊，于是我重新想。。。
(⊙v⊙)嗯
感觉问题不大啊，我依然跑拓扑图，然后在跑之前dfs一次树，把k值更新一下就好了嘛
感觉很对啊
最后要加上一点点优化，就是类似于并查集的路径压缩，这样可以省去许多跳的时间
于是这题就可以A了
#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> #include<queue> using namespace std; const int N=100005; struct qq{int x,y,last;}e[N]; int num,last[N]; int n; int k[N]; int mymax (int x,int y){return x>y?x:y;} int mymin (int x,int y){return x<y?x:y;} void init (int x,int y) { num++; e[num].x=x;e[num].y=y; e[num].last=last[x]; last[x]=num; } int dep[N]; void dfs (int x) { for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; dep[y]=dep[x]+1; dfs(y); } } void lalal1 (int x)//更新k值 { for (int u=last[x];u!=-1;u=e[u].last) { int y=e[u].y; lalal1(y); k[x]=mymin(k[x],k[y]); } } int fa[N]; int ru[N]; queue<int> q; bool lalal[N]; int f[N]; int find (int x) { if (lalal[x]==false) return x; f[x]=find(f[x]); return f[x]; } void solve () { int ans=0; for (int u=1;u<=n;u++) if (ru[u]==0) q.push(u); while (!q.empty()) { int x=q.front();q.pop(); ru[fa[x]]--;if (fa[x]!=0&&ru[fa[x]]==0) q.push(fa[x]); if (lalal[x]==true) continue; ans++; int xx=x; do { lalal[x]=true; x=find(x); }while (dep[x]>=k[xx]); } printf("%d\n",ans); } int main() { memset(lalal,false,sizeof(lalal)); memset(ru,0,sizeof(ru)); num=0;memset(last,-1,sizeof(last)); scanf("%d",&n); for (int u=2;u<=n;u++) { int x; scanf("%d",&x); init(x,u); f[u]=x; fa[u]=x;ru[x]++; } dep[1]=1;dfs(1); for (int u=1;u<=n;u++) { int x; scanf("%d",&x); k[u]=mymax(1,dep[u]-x+1); } lalal1(1); solve(); return 0; }
