解题思路

树结构与约束处理：

无向边（标记为 $5/6$）表示任务冲突，不能同天完成。
有向边 $u \to v$（$d$ 标记为 $2/4$，$u$ 标记为 $1/3$）表示优先级约束，$u$需在$v$前完成。

最长有向路径计算：

通过 DFS 遍历每个节点，计算以该节点为起点的最长有向路径长度 $k$。

任务调度可行性判断：

使用动态规划判断在 $k$天内是否可行。定义 $f[u]$ 和 $g[u]$ 分别表示以节点 $u$ 为根的子树中，调度所需的最长链长度（考虑不同方向的约束）。
对无向边的子节点，按特定顺序排序后计算最优解，确保冲突约束下的天数不超过 $k$。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define M(a,b) make_pair(a,b)
#define F first
#define S second
const int oo=0x3f3f3f3f;
vector<pair<int,int> > e[210],opt;
int n,k,root,fa[210],dfs1[210],f[210],g[210];
bool cmp_f(pair<int,int> p1,pair<int,int> p2)
{
	return p1.F<p2.F;
}
bool cmp_s(pair<int,int> p1,pair<int,int> p2)
{
	return p1.S<p2.S;
}
bool init()
{
	int u,v,i;
	bool flag=0;
	char c;
	n=0;
	memset(fa,0,sizeof(fa));
	for (i=0;i<=205;i++)
		e[i].clear();
	while (scanf("%d",&u)&&u)
	{
		n=max(n,u);
		flag=1;
		while (scanf("%d",&v)&&v)
		{
			n=max(n,v);
			fa[v]=u;
			c=getchar();
			switch (c)
			{
			case ' ':
				e[u].push_back(M(v,5));
				e[v].push_back(M(u,6));
				break;
			case 'd':
				e[u].push_back(M(v,2));
				e[v].push_back(M(u,4));
				break;
			case 'u':
				e[u].push_back(M(v,1));
				e[v].push_back(M(u,3));
				break;
			}
		}
	}
	for (i=1;i<=n;i++)
		if (!fa[i]) root=i;
	return flag;
}
int dfs(int u)
{
	if (dfs1[u]) return dfs1[u];
	dfs1[u]=1;
	int i,x;
	for (i=0;i<e[u].size();i++)
		if ((x=e[u][i].S)==2||x==3)
			dfs1[u]=max(dfs1[u],dfs(e[u][i].F)+1);
	return dfs1[u];
}
void make()
{
	memset(dfs1,0,sizeof(dfs1));
	k=0;
	int i;
	for (i=1;i<=n;i++)
		k=max(k,dfs(i));
}
void dfs2(int u)
{
	vector<pair<int,int> > opt;
	int f1=0,g1=0,i,j,v,ff,gg,x;
	f[u]=g[u]=oo;
	for (i=0;i<e[u].size();i++)
	{
		if (e[u][i].S==2)
		{
			dfs2(v=e[u][i].F);
			f1=max(f1,f[v]);
		}
		if (e[u][i].S==1)
		{
			dfs2(v=e[u][i].F);
			g1=max(g1,g[v]);
		}
		if (e[u][i].S==5)
		{
			dfs2(v=e[u][i].F);
			opt.push_back(M(f[v],g[v]));
		}
	}
	if (opt.empty())
	{
		if (f1+g1+1<=k)
		{
			f[u]=f1+1;
			g[u]=g1+1;
		}
		return;
	}
	sort(opt.begin(),opt.end(),cmp_f);
	gg=0;
	for (i=opt.size()-1;i>=-1;i--)
	{
		if (i!=(opt.size()-1))
			gg=max(gg,opt[i+1].S);
		if (i>=0) x=max(f1,opt[i].F);
		else x=f1;
		if (x+max(gg,g1)+1<=k)
			f[u]=min(f[u],x+1);
	}
	sort(opt.begin(),opt.end(),cmp_s);
	ff=0;
	for (i=opt.size()-1;i>=-1;i--)
	{
		if (i!=opt.size()-1) ff=max(ff,opt[i+1].F);
		if (i>=0) x=max(g1,opt[i].S);
		else x=g1;
		if (x+max(ff,f1)+1<=k)
			g[u]=min(g[u],x+1);
	}
}
bool ok()
{
	dfs2(root);
	return f[root]<oo;
}
int main()
{
	while (init())
	{
		make();
		if (ok()) printf("%d\n",k);
		else printf("%d\n",k+1);
	}
}