再次被卡评测滚粗啦

Day 0

早上原来想看一看以前做过的题然后背一背板的，但没看多久后还是打起了细胞吞噬小Gemo。。然后吔了个饭就上车了、、

车上原来想打kenji的，可是没打多久就晕车了，于是就睡了会，醒来觉得清醒了很多，就又打了会kenji，然后发现又晕车了，于是又睡了会。。这样做了四个多小时的车到了衢州

然后吔了个饭，感觉还可以，苹果还挺好吃的。。然后和YY大爷去操场逛了一圈，发现只有一群裸男在打篮球，像菜地一样的足球场根本没有人踢足球，就又散步回来了，但还是晚到了集合地点，RP--

到宾馆和黈力、wtz、nbd打了两局天梯，都输了，大概是因为我这种傻逼分太高了却整天送吧。。然后第三局的时候我电脑爆掉了，就不打了。。结果第三局他们就赢了、、

然后晚上看了下板，图论看了下tarjan，基环树觉得联赛不考就没看，数论看了下CRT就被YY大爷催着睡觉了

Day 1

吔完早饭就去考场了，但是一直没有找到考场的入口。。进考场的时候发现一堆人已经开始试机了，赶紧打了一堆模板。。然后发现很快就发密码了，卧槽怎么这么早，离比赛开始还有20分钟啊。。这老师好善良啊。。

但是我试了2分钟还是没打开题，只好让老师来帮忙。。太愚蠢了

看了一下，T1大概就是送分题，T2就是找基环树环吧，T3大概就是码农题

8:20的时候老师说可以开始答题了，这没有搞错吧。。提早了10分钟哎、、

T1写了5分钟，第一发WA了，把n*n写成n了

T2原来写了个基环树找环，但是总是写不对，改了一会决定直接写tarjan，但还是没有过大样例。。

真是日了狗了，这TM还有两个环？想了5分钟发现原来还有多个基环树，要找一个最小的环啊。。多谢大样例，要不然就爆零了。。

写完T2还没到9点，就直接来做T3了

看到1G的内存吓傻了，觉得状压没什么希望，就HASH搞

但写了5分钟发现HASH好难写啊。。先写一个暴力算了、、

想了想可以直接把三张的、四张的顺子先打，剩下的傻逼打法打掉就可以了吧

就麻麻麻，加了一些小优化，写了不到半小时，三个样例都一遍过了，好爽~

然后试了下n=23，发现好快啊，10组随机一秒多就能跑出来啦

上了个厕所冷静一下，然后回来查了下T1，觉得没必要查，就去查了下T2，写了个对拍拍一下，也没有什么问题

继续看T3，发现了几个小错误，并做了几个小优化，反复阅读了题目，觉得凭借自己的语文水平，大王和小王应该不算对子

最后1H回去看了看T2，发现tarjan似乎有点写错了，is[x]没有赋为0，但似乎不赋0也没错。。

最后看了看T3，继续加了些优化，现在大概100组最大数据都只有2S多了，就算最差的10组数据也就0.8S

最后20分钟就一直颓，检查了四五遍文件名。。最后10分钟都不想看了，开始重新读题，看看有没有错

结果突然老师就说停止考试了，而时间明明才11:50啊，吓死了赶紧检查一遍文件就走了。。真是日狗，原来这台电脑慢10分钟。。

下午回到宾馆，似乎没人打gemo的样子，就看了会足球。。然后发现我T3似乎四带一一次出啦？好虚

然后YY大爷醒来，然后就把网线给他用了。。下午就一直没打Gemo。。似乎没有我黈力又赢了、、

晚上在YY大爷的怂恿下去了一家大饭店吃饭，似乎也不是很贵的样子、、

然后回来好不容易要回了网线，打了会Gemo，然后看了下今天题目，谢天谢地，没有n=5~9的数据，这样估计挺难×了我的傻逼写法吧。。

发现没时间了，赶紧背几个不太会的板就睡了、、

Day 2

早上有经验了就第一个进考场，打了十多个模板，觉得够用了

题发下来开始看，T1好难啊，感觉比前几年难多了。。T2好神啊，估计是个挺难的DP，T3似乎是树剖？我没看错吧

T1冷静下来想了会，觉得可以二分然后贪心，就写了一下，过了两个样例，但是大样例很傻比的样子有点虚

然后T2觉得有点神，暂时不太会，部分分也不太多，DP暂时推不出，就去写T3的暴力了

T3暴力写了一大半发现是n^2lgn的没什么希望了，就想T2不会做没什么希望了，就回去艹T2

直接开始推DP方程，一开始推了个nmk^2的，然后发现似乎可以预处理后前缀和优化，然后又发现我推得似乎是nmk^3的，然后发现似乎要二维前缀和优化，但我不知道是不是对的。。

就开始写，刚写没多久就发现打出了一行6，原来是我一打回车就输出6了。。然后让老师来看也没什么办法，然后过了5分钟又自动好了。。真是醉了

写了20多分钟写出来，结果小样例没过，调了一会还是没过。。

重新回来想，觉得循环要从0开始，重新试了下，又调了一会才过了小样例

然后测了下大样例，发现也过了，虽然自己并不能证明这个DP的正确性，但过了大样例还是不虚了

觉得非常爽，就去上了下厕所，顺便YY了一下T1的正确性，觉得靠谱

回来开始干写了一半的T3，觉得没有思路了，感觉只能排序后直接上树剖

但是一开始的预处理似乎也只会倍增的，不过这没关系，树剖两个log倍增一个log，你卡我不成？

然后直接写树剖，但是写完后连样例都过不了，感觉非常虚，觉得这题爆零就没什么希望了

开始调试，发现树剖连轻链和重链都写反了，真是没希望了。。

然后发现树剖LCA各种写炸，查了好久才查出来。。

总算过了小样例，但是大样例还是错了

输出调试一下，发现我树剖只写了个DFS序，没有记录反过来的to，以至于把pos和to搞反了。。

改了一下，发现大样例还是过不了，真是日了狗了

输出调试一下，发现我的思路错啦。。我每次直接在上面减一个最大值判，然而这是不靠谱的

我应该判断一下是删原来的路好还是用新的路好，这样应该能A了吧。。

就在原来的程序上又改了改，总算过了大样例。。然后删了一些奇怪的话

觉得有点虚，写复制了一个暴力开始对拍，拍了几组就错了。。

我来看一看。。不科学啊，原来是倍增LCA没有把i弄到0，这都能过大样例真是醉了。。

然后改了下，总算拍不出错了。。试了下300000的随机数据，要1S加，估计没什么希望了，这时还有50min

写了个读入优化，这是我第一次写读入优化好紧张呢。。一开始写炸了，回忆了一下模板，总算改对啦

发现随机数据快了一半，竟然有一半多的时间用在了读入上。。然后还是对读入优化有点怀疑，就一直拍，大概还有40min

然后就回去看了会T1和T2，T1原来想写个DP对拍的，但发现DP写不出来，觉得二分是对的就不管了

最后继续看T3，觉得也没什么办法了，就这样吧。。联赛写树剖也是无奈之举啊、、

最后一直都很虚，到最后我也没能证明T3树剖的正确性，反正拍不出来应该不会错太多吧。。

吃完饭出来就下起大雨了，直接冲上车连电脑都没从箱子里拿出来

在车里没有电脑啥都干不了，就先睡了一觉，又睡了一觉，觉得再睡没什么希望了，就想了下联赛的几道题的正确性，感觉还是靠谱的，除了T3的四带一

回来坐了将近6H的车，总算回到了学校。。

后记

CCF的评测机实在是太快了，Day2T2卡了我10分，T3卡了5分，然后就滚粗了QAQ，早知道这样就把T2优化一下了。。

总的来说，这次联赛的题都不是很难，又有大数据，所以只要写了就不太容易写错，虽然自己智商太低用了一些愚蠢的算法，代码写得长且丑，也被卡掉了一些分，但最少没有爆题，也还是可以接受的。。

接下来就是要提高智商了，做些难度高一些的题，RP++

解题报告也写好了，贴在后面吧

NOIP2015提高组解题报告

T1 神奇的幻方

【题目大意】 告诉你幻方的构造方法，给出$N*N$幻方的方案。$N\leq39$且为奇数。

【解题说明】 直接模拟即可

#include<cstdio>
int n,m,i,j,x,y,a[55][55];
int main(){
       scanf("%d",&n);m=n*n;x=1;y=(n+1)/2;a[x][y]=1;
       for(i=2;i<=m;a[x][y]=i++)
              if(x==1&&y!=n)x=n,y++;else if(x!=1&&y==n)y=1,x--;
              else if(x==1&&y==n)x++,a[x][y]=i;else if(!a[x-1][y+1])x--,y++;else x++;
       for(i=1;i<=n;i++)
              for(j=1;j<=n;j++){
                     printf("%d",a[i][j]);
                     if(j<n)printf(" ");else puts("");
              }
}

【时间复杂度】 $O(n^2)$  【空间复杂度】 $O(n^2)$

【思想难度】 6 【编程难度】 8 【总用时】5 min

T2 信息传递

【题目大意】 在若干颗基环+内向树中找到一个最小的环。$N\leq200000$，无自环。

【解题说明】

30分做法：Floyd找最小环

60分做法：每个点BFS一遍就可以了

100分做法：

①     基环+内向树的找环 直接套模板即可

②     Tarjan 找到一个最小的size不为1的强连通分量即可

③     BFS/DFS 在暴力的基础上多加一个标记即可

④     并查集 据说这也能做

#include<cstdio>
#include<algorithm>
#define N 222222
using namespace std;
int n,i,tm,tp,now,ans,sz,to[N],dfn[N],low[N],st[N];bool is[N];
void dfs(int x){
	dfn[x]=low[x]=++tm;st[++tp]=x;is[x]=1;
	int y=to[x];
	if(!dfn[y])dfs(y),low[x]=min(low[x],low[y]);
	else if(is[y])low[x]=min(low[x],dfn[y]);
	if(low[x]==dfn[x]){
		for(sz=now=0;now!=x;)now=st[tp--],sz++;
		if(sz>1)ans=min(ans,sz);
	}
}
int main(){
	for(ans=1e9,scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&to[i]);
	for(i=1;i<=n;i++)if(!dfn[i])dfs(i);
	printf("%d",ans);
}

【时间复杂度】 $O(n)$  【空间复杂度】 $O(n)$

【思想难度】 25 【编程难度】 25 【总用时】15 min

T3 斗地主

【题目大意】 给你一副斗地主手牌，问你最快几次出完，数据随机，牌数不超过23。

【解题说明】

30分做法：$N\leq4$，没有顺子，直接贪心即可。

60~70分做法：

①     写一个非常暴力的暴力。

②     写一个非常暴力的状压DP。

90分做法：状压DP再小小地优化一下，由于每种牌在读入数据出来后上限已经固定了，最差情况下是每种牌平均分布，状态表示需要$3^9*2^5=629856$，转移再加一些优化，理论上能过，但CCF的机子太慢了会被卡10分

100分做法：

①     还是暴力，单牌和对牌最后处理就可以了，剩下的各种情况讨论，随机数据轻松跑出。

②     暴力+贪心，暴力枚顺子，剩下的牌肯定是可以贪心的，随便搞一搞就可以了

#include<cstdio>
#include<algorithm>
#include<cstring>
#define mxh 1000000007
using namespace std;
int ans,T,n,i,x,y,pai[6],cnt[15];
void find(int step){
	int i,j,k,w;
	if(step>=ans)return;
	ans=min(ans,step+pai[1]+pai[2]+pai[3]+pai[4]);
	if(pai[4])for(i=2;i<=14;i++)if(cnt[i]==4){
		pai[4]--;cnt[i]-=4;
		if(!pai[3]&&!pai[4]&&!pai[1]&&pai[2]<=1){
			ans=min(ans,step+1);
			pai[4]++;cnt[i]+=4;
			return;
		}
		for(j=1;j<=14;j++)if(cnt[j]){
			pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++;
			for(k=j;k<=14;k++)if(cnt[k]){
				pai[cnt[k]]--;cnt[k]--;pai[cnt[k]]++;
				find(step+1);
				pai[cnt[k]]--;cnt[k]++;pai[cnt[k]]++;
			}
			pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++;
		}
		if(pai[2]||pai[3]||pai[4])for(j=2;j<=14;j++)if(cnt[j]>1){
			pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++;
			for(k=j;k<=14;k++)if(cnt[k]>1){
				pai[cnt[k]]--;cnt[k]-=2;pai[cnt[k]]++;
				find(step+1);
				pai[cnt[k]]--;cnt[k]+=2;pai[cnt[k]]++;
			}
			pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++;
		}
		pai[4]++;cnt[i]+=4;
	}
	if(pai[3])for(i=2;i<=14;i++)if(cnt[i]>=3){
		pai[cnt[i]]--;cnt[i]-=3;pai[cnt[i]]++;
		find(step+1);
		for(j=1;j<=14;j++)if(cnt[j]){
			pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++;
			find(step+1);
			pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++;
		}
		if(pai[2]||pai[3]||pai[4])for(j=2;j<=14;j++)if(cnt[j]>1){
			pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++;
			find(step+1);
			pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++;
		}
		pai[cnt[i]]--;cnt[i]+=3;pai[cnt[i]]++;
	}
	if(pai[3]+pai[4]>=2)for(i=3;i<14;i++)if(cnt[i]>=3&&cnt[i+1]>=3){
		pai[cnt[i]]--;cnt[i]-=3;pai[cnt[i]]++;w=i;
		for(j=i+1;cnt[j]>=3&&j<=14;j++){
			pai[cnt[j]]--;cnt[j]-=3;pai[cnt[j]]++;
			find(step+1);w=j;
		}
		for(j=i;j<=w;j++){
			pai[cnt[j]]--;cnt[j]+=3;pai[cnt[j]]++;
		}
	}
	if(pai[2]+pai[3]+pai[4]>=3)for(i=3;i<13;i++)if(cnt[i]>=2&&cnt[i+1]>=2&&cnt[i+2]>=2){
		pai[cnt[i]]--;cnt[i]-=2;pai[cnt[i]]++;
		pai[cnt[i+1]]--;cnt[i+1]-=2;pai[cnt[i+1]]++;w=i+1;
		for(j=i+2;cnt[j]>=2&&j<=14;j++){
			pai[cnt[j]]--;cnt[j]-=2;pai[cnt[j]]++;
			find(step+1);w=j;
		}
		for(j=i;j<=w;j++){
			pai[cnt[j]]--;cnt[j]+=2;pai[cnt[j]]++;
		}
	}
	if(pai[1]+pai[2]+pai[3]+pai[4]>=5)for(i=3;i<11;i++)if(cnt[i]&&cnt[i+1]&&cnt[i+2]&&cnt[i+3]&&cnt[i+4]){
		pai[cnt[i]]--;cnt[i]--;pai[cnt[i]]++;
		pai[cnt[i+1]]--;cnt[i+1]--;pai[cnt[i+1]]++;
		pai[cnt[i+2]]--;cnt[i+2]--;pai[cnt[i+2]]++;
		pai[cnt[i+3]]--;cnt[i+3]--;pai[cnt[i+3]]++;w=i+3;
		for(j=i+4;cnt[j]&&j<=14;j++){
			pai[cnt[j]]--;cnt[j]--;pai[cnt[j]]++;
			find(step+1);w=j;
		}
		for(j=i;j<=w;j++){
			pai[cnt[j]]--;cnt[j]++;pai[cnt[j]]++;
		}
	}
}
int main(){
	for(scanf("%d%d",&T,&n);T--;){
		ans=12;
		memset(cnt,0,sizeof(cnt));
		memset(pai,0,sizeof(pai));
		for(i=1;i<=n;i++){
			scanf("%d%d",&x,&y);
			if(x==1)x=14;
			if(x==0)x=1;
			cnt[x]++;
		}
		for(i=1;i<=14;i++)pai[cnt[i]]++;
		find(0);
		printf("%d\n",ans);
	}
}

【时间复杂度】 O(？)  【空间复杂度】 O(？)

【思想难度】 27 【编程难度】 51 【总用时】45 min

T4 跳石头

【题目大意】给你一排$N$块石头，你可以移走$M$块石头，使得最小的两块石头之间的距离尽可能长，$N,M\leq50000$。

【解题说明】

20分做法：直接暴力即可

50分做法：考虑DP，$f[i][j]$表示在前$i$块石头移走$j$块石头的最短距离，转移即可

60分做法：考虑贪心，每次删除间距最小的，用堆维护，由于数据比较弱可以得60分

100分做法：考虑二分答案后贪心，先二分这个距离使其变为判断可行性问题，然后从前往后扫，一旦这个石头到上一个选的石头的距离小于这个二分的答案就把这块石头移走

这样显然是正确的，很容易证明先移一定比后移好，所以这个算法是正确的

#include<cstdio>
int L,n,m,i,w,l,r,mid,pos,ans,a[55555];
bool ok(int x){
	for(pos=w=0,i=1;i<=n;i++)if(a[i]-pos<x)w++;else pos=a[i];
	return w<=m;
}
int main(){
	for(scanf("%d%d%d",&L,&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);a[++n]=L;
	for(l=1,r=L;l<=r;)if(ok(mid=l+r>>1))ans=mid,l=mid+1;else r=mid-1;
	printf("%d",ans);
}

【时间复杂度】 $O(nlgL)$  【空间复杂度】 $O(n)$

【思想难度】 30 【编程难度】 23 【总用时】10 min

T5 子串

【题目大意】有两个字符串$A$和$B$。现在要从字符串$A$中取出$k$个互不重叠的非空子串，然后把这$k$个子串按照其在字符串$A$中出现的顺序依次连接起来得到一个新的字符串，问有多少种方案可以使得这个新串与字符串$B$相等。$|A|\leq1000$，$|B|leq200$，$k\leq200$。

【解题说明】

特殊的10分做法：$k=1$，所以直接扫一遍判断就可以了

特殊的20分做法：$k=2$，所以枚举分隔点再扫一遍判断就可以了

特殊的20分做法：$k=m$，所以从前往后扫一遍DP统计一下方案就可以了

70分做法：考虑dp，用$f[i][j][k]$表示$A$串匹配到第$i$个字符，$B$串匹配到第$j$个字符，已经取了$k$个互不重叠的非空子串的方案数，那么$f[i][j][k]=\sum f[i-w-o][j-w][k-1]$(w=1-A[i]和B[j]的最大后缀匹配，$i-w-o\geq0$)，$f[0][0][0]=1$，这样直接转移的复杂度是$O(nm^3k)$的，把$o$这一维前缀和转移一下，就是$O(nm^2k)$的，可以通过70分的数据。

90分做法：再把$w$也前缀和转移掉，就可以通过90分的数据。

100分做法：加一个滚动数组，然后再卡一卡常，就可以通过100分的数据。

当然其它很多DP方法也是能过哒。

#include<cstdio>
#define mxh 1000000007
int i,j,w,n,m,k,h,ans,pre[1111][222],f[2][1111][222];char a[1111],b[1111];
int main(){
	scanf("%d%d%d%s%s",&n,&m,&k,a+1,b+1);
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++){
			for(w=j;w&&i-(j-w)&&a[i-(j-w)]==b[w];w--);
			pre[i][j]=j-w;
		}
	f[1][0][0]=1;
	for(j=0;j<=n;j++)for(w=0;w<=m;w++)f[1][j][w]=(f[1][j][w]+(j?f[1][j-1][w]:0))%mxh;
	for(j=0;j<=n;j++)for(w=0;w<=m;w++)f[1][j][w]=(f[1][j][w]+((j&&w)?f[1][j-1][w-1]:0))%mxh;
	for(i=1;i<=k;h^=1,i++){
		for(j=0;j<=n;j++)for(w=0;w<=m;w++)
			f[h][j][w]=(((j&&w)?f[h^1][j-1][w-1]:0)-(((j-pre[j][w])&&(w-pre[j][w]))?f[h^1][j-pre[j][w]-1][w-pre[j][w]-1]:0)+mxh)%mxh;
		if(i!=k){
		for(j=1;j<=n;j++)for(w=1;w<=m;w++)
			f[h][j][w]=(f[h][j][w]+f[h][j-1][w])%mxh;
		for(j=1;j<=n;j++)for(w=1;w<=m;w++)
			f[h][j][w]=(f[h][j][w]+f[h][j-1][w-1])%mxh;
		}
	}
	for(i=1;i<=n;i++)ans=(ans+f[h^1][i][m])%mxh;
	printf("%d",ans);
}

【时间复杂度】 $O(nmk)$  【空间复杂度】 $O(nm)$

【思想难度】 39 【编程难度】 30 【总用时】45 min

T6 运输计划

【题目大意】 给你一颗带权树和若干条航线，你可以使一条边的权值变为$0$，然后使得最长航线最短，$N\leq300000$。

【解题说明】

①20分做法：$m=1$，直接找到这条路然后删掉这条路上的最长边就可以了

②50~60分做法：枚举删除哪条边，然后用倍增的方法暴力求出每条航线的代价就可以了，复杂度$O(nlgn+nmlgn)$

③ 特殊的40分做法：为一条链，可以线段树随便维护一下，结合算法②可以获得80分。

④45~60分做法：考虑把初始航线长度从小到大排序，二分这个答案，然后用数据结构判断一下可行性就可以了，简单的方法是树链剖分，这样的时间复杂度是$O(mlg^3n)$的，理论上可以通过95分的数据，但由于CCF的评测机很慢，只能通过45~60分的数据。

⑤65分做法：很明显答案只可能在最长的一条链上的某一条边，那么贪心选取最大的一条边试一下，由于数据比较弱，可以得到65分

⑥65分+做法：按照⑤的方法多选几条边试一下，可以得到更好的分数

⑦95分做法：把航线从大到小排序，我们要求的就是当前航线的交中的最大值，这个可以用树链剖分维护然后分类讨论一下是选择新的交的最大值好还是旧的交的最大值和新航线的长度好，如果新航线单独算一条更好，那么就退出并得到了答案，时间复杂度$O(nlgn+mlg^2n)$。

⑧95分做法：同样把航线从大到小排序，仍然要求交，可以用LCA大力分类讨论一下得到航线的交，这样时间复杂度是$O(nlgn+mlgn)$的，但由于常数比较大，还是不能通过全部的数据。

⑨100分做法：据说可以用直接线段树维护，由于线段树很快，就可以艹过全部数据啦。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 300300
using namespace std;
int n,m,i,j,x,y,z,tp,pt,ww,tot,sum,ans,bl[N],sz[N],h[N],pos[N],to[N],fa[N][19],g[N][19],fir[N],va[N<<1],ne[N<<1],la[N<<1],val[N<<2];bool lz[N<<2];
struct P{int x,y,z;}p[N];struct Q{int l,r;}q[N];char ch;
void read(int &x){
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
}
bool cmp(P a,P b){return a.z>b.z;}bool cmp2(Q a,Q b){return a.l<b.l;}
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
void dfs(int x){
	sz[x]=1;
	for(int i=1;i<=18;i++)fa[x][i]=fa[fa[x][i-1]][i-1],g[x][i]=g[x][i-1]+g[fa[x][i-1]][i-1];
	for(int i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i]){
		fa[la[i]][0]=x;g[la[i]][0]=va[i];h[la[i]]=h[x]+1;
		dfs(la[i]);
		sz[x]+=sz[la[i]];
	}
}
void dfs2(int x,int f){
	pos[x]=++tp;to[tp]=x;bl[x]=f;
	int i,now=0;
	for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i]&&sz[la[i]]>sz[now])now=la[i];
	if(!now)return;
	dfs2(now,f);
	for(i=fir[x];i;i=ne[i])if(fa[x][0]!=la[i]&&now!=la[i])dfs2(la[i],la[i]);
}
int lca(int x,int y){
	sum=0;
	if(h[x]<h[y])swap(x,y);int i,t=h[x]-h[y];
	for(i=0;i<=18;i++)if(t&(1<<i))sum+=g[x][i],x=fa[x][i];
	for(i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])sum+=g[x][i]+g[y][i],x=fa[x][i],y=fa[y][i];
	if(x==y)return sum;else{
		sum+=g[x][0]+g[y][0];
		return sum;
	}
}
void bt(int k,int l,int r){
	if(l==r){val[k]=g[to[l]][0];return;}
	int mid=l+r>>1;
	bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
	val[k]=max(val[k<<1],val[k<<1|1]);
}
void add(int k,int l,int r,int x,int y){
	if(x>y||x==0)return;
	if(x<=l&&r<=y){
		val[k]=0;lz[k]=1;
		return;
	}
	if(lz[k]){val[k<<1]=val[k<<1|1]=0;lz[k<<1]=lz[k<<1|1]=1;}
	int mid=l+r>>1;
	if(x<=mid)add(k<<1,l,mid,x,y);
	if(y>mid)add(k<<1|1,mid+1,r,x,y);
	val[k]=max(val[k<<1],val[k<<1|1]);
}
int main(){
	for(read(n),read(m),i=1;i<n;i++)read(x),read(y),read(z),ins(x,y,z),ins(y,x,z);
	dfs(1);dfs2(1,1);
	for(i=1;i<=m;i++)read(p[i].x),read(p[i].y),p[i].z=lca(p[i].x,p[i].y);
	bt(1,1,n);sort(p+1,p+m+1,cmp);
	for(i=1;i<=m;i++)if(p[i].z>ans){
		ww=val[1];pt=0;x=p[i].x;y=p[i].y;
		for(;bl[x]!=bl[y];x=fa[bl[x]][0]){
			if(h[bl[x]]<h[bl[y]])swap(x,y);
			q[++pt].l=pos[bl[x]];q[pt].r=pos[x];
		}
		if(pos[x]>pos[y])swap(x,y);
		if(pos[x]!=pos[y])q[++pt].l=pos[x]+1,q[pt].r=pos[y];
		sort(q+1,q+pt+1,cmp2);
		for(j=1;j<=pt;j++)add(1,1,n,q[j-1].r+1,q[j].l-1);
		add(1,1,n,q[pt].r+1,n);
		if(max(p[1].z-ww,p[i].z)<=p[1].z-val[1]){
			ans=max(ans,max(p[1].z-ww,p[i].z));
			break;
		}else ans=max(ans,p[1].z-val[1]);
	}
	printf("%d",ans);
}

【时间复杂度】 $O(nlgn+mlgn)$  【空间复杂度】 $O(n)$

【思想难度】 35 【编程难度】 52 【总用时】75 min

• 相关文章推荐
• 全局相关文章