首页 > 其他 > 详细

题解报告——离家出走

时间:2018-07-21 20:56:07      阅读:36      评论:0      收藏:0      [点我收藏+]

标签:事件类型   merge   clas   get   fat   优化   pan   getc   距离   

离家出走

时间限制: 2000 ms         内存限制: 262144 KB

【题目描述】

企鹅豆豆考试爆零了,心态爆炸的他准备离家出走。

贫穷的企鹅国有 N 座城市,一开始城市之间没有道路连接不能通行。随着时间推移,一些道路逐渐建立。但由于国家财力实在不足,所以随时随地任意两座城市最多只有一条路径可以互相到达。

每次豆豆考试爆炸,他都想从考场里跑到离考场最远的一个城市去。当然豆豆每次都会想知道,最远的且可以到达的城市离考场所在城市有多远?

奇妙的事情是,企鹅国的每一条道路长度都是 1。

【输入】

第一行一个整数 type,表示数据类型。

接下来第二行两个整数 N,Q,表示城市个数和事件个数。

接下来 Q 行,先读入一个整数 op,表示事件类型。

如果 op=1,那么接着有两个整数 u,v,表示城市 u 和城市 v 之间建立了一条新的道路。

如果 op=2,那么接着有一个整数 u,表示这次考试的考场在城市 u,豆豆想知道最远的城市离考场有多远。

如果 type=1,令上一次 op=2 时的答案为 lastans,那么对于输入的每一个 u 或者 v 都需要异或上 lastans。(lastans 初始为 0。)

如果 type=0,那么不需要进行其余额外操作。

【输出】

对于每次 op=2 的询问,输出一行一个整数表示离考场最远的城市距离考场的距离。

【输入样例】

0
5 10
1 4 5
2 3
2 5
2 1
1 5 3
1 1 4
2 3
2 5
1 5 2
2 1

【输出样例】

0
1 
0
3
2
3

【提示】

对于 20%的输入数据:N≤5000,Q≤10000。

对于 50%的输入数据:N≤100000,Q≤200000。

对于另外 20%的输入数据:type=0。

对 100%的输入数据:N≤300000,Q≤500000,道路的修建会满足,随时随地图中不存在环。


 

【思路分析】

暑假集训考试,成功实现暴力操标算,我的暴力查询得到了buff加成,成功超越去写标算的同学,当然还是没有凯爷的标算快(谁叫人家是集训队的。。。)

我们很容易发现这道题的是一颗树,每次连边就是树的合并,当然可以用LCT大力搞一搞(复杂度nlogn),然而考试时蒟蒻的我根本打不出LCT,所以我们想可以进行子树的合并,不难想到用启发式合并去优化,启发式合并就是选择较小的子树接到大的子树上,然后dfs更新较小树的信息(深度,树根,父亲)。然后在向上更新较大子树的子树大小(只用更新连接点的祖先),我们发现因为每次选择较小的更新,大小不会超过一半,所以每个节点的更新次数不会超过logn次,然后就很优秀了(然而考场上没想到怎么证复杂度就去写了,真的虚。。。)

对于查询操作,我们维护两个信息,一个是dis[i] 记录节点i的子树中最深叶子的深度,还有一个dep[i]记录每个节点的深度,查询一个点时就向上跳father就可以了。

 


 

【代码实现】

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<algorithm>
 4 using namespace std;
 5 void read(int &v)
 6 {
 7     int f;char ch;
 8     while(!isdigit(ch=getchar())&&ch!=-); ch==-?(v=0,f=-1):(v=ch-0,f=1);
 9     while(isdigit(ch=getchar())) v=v*10+ch-0;v=v*f;
10 }
11 const int N=3e5+5;
12 struct sd{
13     int next,to;
14 }edge[N<<1];
15 int head[N],fa[N],dis[N],root[N],siz[N],dep[N],n,cnt,lastans,q;
16 void add_edge(int x,int y)
17 {
18     edge[++cnt].to=y;
19     edge[cnt].next=head[x];
20     head[x]=cnt;
21 }
22 void dfs(int v,int ff,int rt)
23 {
24     fa[v]=ff,root[v]=rt,siz[v]=1,dep[v]=dep[ff]+1,dis[v]=0;
25     for(int i=head[v];i;i=edge[i].next)
26     {
27         int to=edge[i].to;
28         if(to!=ff)
29         {
30             dfs(to,v,rt);
31             siz[v]+=siz[to];
32             dis[v]=max(dis[v],dis[to]+1);
33         }
34     }
35 }
36 void update(int v,int son,int sss)
37 {
38     siz[v]+=sss,dis[v]=max(dis[v],dis[son]+1);
39     if(root[v]==v) return;
40     update(fa[v],v,sss);
41 }
42 void merge(int a,int b)
43 {
44     add_edge(a,b),add_edge(b,a);
45     dfs(b,a,root[a]);
46     siz[a]+=siz[b],dis[a]=max(dis[a],dis[b]+1);
47     if(root[a]!=a) update(fa[a],a,siz[b]);
48 }
49 void ask(int v,int goal)
50 {
51     if(root[v]==v) return;
52     int ff=fa[v];bool gg=1;
53     for(int i=head[ff];i;i=edge[i].next)
54     {
55         int to=edge[i].to;
56         if(to!=fa[ff]&&to!=v)
57         {
58             gg=0;
59             lastans=max(lastans,dep[goal]-dep[ff]+dis[to]+1);
60         }
61     }
62     if(gg) lastans=max(lastans,dep[goal]-dep[ff]);
63     ask(ff,goal);
64 }
65 int main()
66 {
67     //freopen("away.in","r",stdin);freopen("away.out","w",stdout);
68     int type,opt,a,b;
69     read(type),read(n),read(q);
70     for(int i=1;i<=n;i++) root[i]=i,fa[i]=i,siz[i]=1,dep[i]=1;
71     while(q--)
72     {
73         read(opt);
74         if(opt==1)
75         {
76             read(a),read(b);
77             if(type) a=a^lastans,b=b^lastans;
78             if(siz[root[a]]<siz[root[b]]) swap(a,b);
79             merge(a,b);
80         }
81         else
82         {
83             read(a);
84             if(type) a=a^lastans;
85             lastans=0;
86             ask(a,a);
87             lastans=max(lastans,dis[a]);
88             printf("%d\n",lastans);
89         }
90     }
91     return 0;
92 }

 

题解报告——离家出走

标签:事件类型   merge   clas   get   fat   优化   pan   getc   距离   

原文:https://www.cnblogs.com/genius777/p/9347912.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号