开开特别喜欢玩一款叫作王者荣耀的游戏,并且多次在高校杯获得冠军。作为冠军打野,开开决定给朋友们出一篇打野路线教程: “首先,作为打野,我们从泉水出发后,应该前往不同的野怪处打野,打完之后再决定下一只野怪打什么。当然,我们知道,同一处的野怪在一定时间内只有一只,所以一旦我们从一处野怪离开后,便没有回头路可走了。此外,每打一只野怪可以获得1点快乐值。刚进入游戏时,我们在泉水的初始快乐值为1点”。 已知,开开在教程中提供了所有可能的打野路线,如果想要尽可能获得更多的快乐,聪明的你可以帮他算一算开开最大的快乐值是多少吗? 开开的其他攻略: ① 开开非常喜欢树,所以包括泉水在内的打野路线为一个树形结构。开开从泉水出发,不断前进,击败遇到的所有野怪,直到无路可走。 ② 泉水和野怪都可以看作树上的一个节点,某些节点之间存在单向边,将所有的节点从1到n编号。 输入格式:
第一行两个正整数n(1<=n<=1e5)和r,分别表示树的节点数和泉水的标号。
接下来n行,每个两个正整数u和v,表示有一条从u到v的边。
输出格式:
一个正整数,开开最大能获得的快乐值。 限制:
空间限制:128MByte 时间限制:1秒 样例:
输入:
5 1 1 2 1 3 3 4 3 5 输出:
3
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int n,numw;
const int N=1e5+100;
struct head
{
int first;
}heads[N];
struct edge
{
int to;
int next;
}edges[N];
int len;
int maxsum=1;
int addrode(int u,int v);
void dfs(int root,int sum);
int main()
cin>>n>>numw;
int u,v;
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&u,&v);
addrode(u,v);
}
dfs(numw,1);
cout<<maxsum;
return 0;
}
int addrode(int u,int v)
{
edges[++len].to = v;
edges[len].next = heads[u].first;
heads[u].first = len;
}
void dfs(int root,int sum)
{
if(heads[root].first == 0)
{
maxsum = max(maxsum,sum);
return;
}
int root1=heads[root].first;
// cout<<heads[root].first<<' ';
while(1)
{
dfs(edges[root1].to,sum+1);
root1 = edges[root1].next;
if(root1 == 0)
break;
}
}