博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
2017.08.11【NOIP提高组】模拟赛B组 小X的佛光
阅读量:4625 次
发布时间:2019-06-09

本文共 3224 字,大约阅读时间需要 10 分钟。

####Description

这里写图片描述
####Input
这里写图片描述
####Output
这里写图片描述
####Sample Input

3 3 1

1 2
2 3
1 2 3
1 1 3
3 1 3

####Sample Output

1

1
3

####Data Constraint

这里写图片描述

###题解:

本题看上去很奇怪,首席先我们看一个题解:
这里写图片描述这里写图片描述
我们发现,本题的数据有分支,于是有的点可以用线段树,有的点可以用Tarjan搞LCA。而且正解特别简单,但是比较弱弱的我,傻逼地打了个树链剖分。
于是我们来讲讲:
首先,我们在题解中发现,求A到C与B到C的答案等于求A到C加B到C减去A到B。
于是我们借用树链剖分的思路,来搞搞,但是本人一时头脑发热,一下子把50%分的方法的一个部分用在的树链剖分里,于是时间变得特别地慢。有兴趣的童鞋可以研究研究。
Code:

uses math;var        i,j,k,l,n,m,num,x,y,tot,ans,gs,a,b,c:longint;        tov,last,next,siz,son,dep,fa,tree,pre,top,f:array[1..800000] of int64;procedure maketree(x,st,en:longint);var        m:longint;begin        if st=en then f[x]:=1	else	begin	        m:=(st+en) div 2;		maketree(x*2,st,m);		maketree(x*2+1,m+1,en);                f[x]:=f[x*2]+f[x*2+1];	end;end;procedure find(x,st,en,l,r:longint);var        m:longint;begin        if (st=l) and (en=r) then ans:=ans+f[x]	else	begin	        m:=(st+en) div 2;		if r<=m then find(x*2,st,m,l,r)		else                begin		        if l>m then find(x*2+1,m+1,en,l,r)			else			begin			        find(x*2,st,m,l,m);				find(x*2+1,m+1,en,m+1,r);		        end;                end;	end;end;procedure dfsfd(v,f,d:longint);var        i,j,k,l:longint;begin        fa[v]:=f;        dep[v]:=d;        siz[v]:=1;        i:=last[v];        while i<>0 do        begin                if tov[i]<>fa[v] then                begin                        dfsfd(tov[i],v,d+1);                        siz[v]:=siz[v]+siz[tov[i]];                        if (son[v]=0) or (siz[tov[i]]>siz[son[v]]) then son[v]:=tov[i];                end;                i:=next[i];        end;end;procedure dfs(v,num:longint);var        i,j,k,l:longint;begin        inc(gs);        tree[v]:=gs;        top[v]:=num;        pre[gs]:=v;        if son[v]=0 then exit;        dfs(son[v],num);        i:=last[v];        while i<>0 do        begin                if tov[i]<>fa[v] then                begin                        if tov[i]<>son[v] then                        begin                                dfs(tov[i],tov[i]);                        end;                end;                i:=next[i];        end;end;function getans(x,y:longint):longint;var        i,j,tx,ty,k:longint;begin        tx:=top[x];        ty:=top[y];        k:=0;        while tx<>ty do        begin                if dep[tx]
dep[y] then begin ans:=0; find(1,1,n,tree[y],tree[x]); k:=k+ans; end else begin ans:=0; find(1,1,n,tree[x],tree[y]); k:=k+ans; end; exit(k);end;procedure insert(x,y:longint);begin inc(tot); tov[tot]:=y; next[tot]:=last[x]; last[x]:=tot;end;begin //assign(input,'0data.in');reset(input); //assign(output,'0data.out');rewrite(output); readln(n,m,num); for i:=1 to n-1 do begin readln(x,y); insert(x,y); insert(y,x); end; maketree(1,1,n); dfsfd(1,0,1); dfs(1,1); for i:=1 to m do begin readln(a,b,c); writeln((getans(a,b)+getans(c,b)-getans(a,c))div 2+1); end;end.

转载于:https://www.cnblogs.com/RainbowCrown/p/11148429.html

你可能感兴趣的文章
django的模板文件需要为utf-8无bom格式
查看>>
Fedora Linux 18 延期至年底
查看>>
Spring Framework 3.2 RC1 发布
查看>>
基于ios开发点餐系统应用(附带源码)
查看>>
Xenia and Weights(深度优先搜索)
查看>>
文件包含漏洞进阶篇
查看>>
JavaScript的self和this使用小结
查看>>
CSS3.0:透明度 Opacity
查看>>
Arduino Wire.h(IIC/ I2C)语法
查看>>
web高并发的解决方案
查看>>
OC中的NSNumber、NSArray、NSString的常用方法
查看>>
android 用ImageSwitcher+Gallery实现图片浏览效果 分类: ...
查看>>
STM32里面的一些小函数——assert_param,PUTCHAR_PROTOTYPE
查看>>
Java分布式锁的三种实现方案(redis)
查看>>
运行客户端程序报读取配置文件出错的解决方案
查看>>
day 5 - 2 字典(dict)练习
查看>>
微引擎的自定义菜单40063错误解决
查看>>
JAVA wait(), notify(),sleep具体解释
查看>>
数据挖掘十大经典算法
查看>>
WebService原理
查看>>