果然我还是最菜的==不接受反驳==
Day1
T1：神奇的幻方
思路：直接模拟即可，由于当前放法只与上一放法有关系，用两个变量记录一下即可。10分钟内切掉==
预计得分：100分
实际得分：100分
#include<cstdio>
#include<algorithm> using namespace std; int n,lx,ly;
int vis[][],a[][]; int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d",&n);
a[][(n+)>>]=;
vis[][(n+)>>]=;
lx=;ly=(n+)>>;
for(int i=;i<=n*n;i++)
{
if(lx==&&ly!=n)
{
a[n][ly+]=i;
vis[n][ly+]=;
lx=n,ly++;
}
else if(lx!=&&ly==n)
{
a[lx-][]=i;
vis[lx-][]=;
lx--;ly=;
}
else if(lx==&&ly==n)
{
a[lx+][ly]=i;
vis[lx+][ly]=;
lx++;
}
else if(lx!=&&ly!=n)
{
if(!vis[lx-][ly+])
{
a[lx-][ly+]=i;
vis[lx-][ly+]=;
lx--;ly++;
}
else
{
a[lx+][ly]=i;
vis[lx+][ly]=i;
lx++;
}
}
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
return ;
}
magic
T2：信息传递
思路：方法有多种。可以用tarjan求最小环，或者用拓扑排序，或者用并查集。以前做过，还写了题解 。感觉这是noip第二题少有的简单题了吧。考场上写的tarjan。
预计得分：100分
实际得分：80分
（是这样的qwq 因为实在win下评测的栈小，而且用的cena栈会更小，于是就出锅了qwq，拿到洛咕上是可以满分的，而且这个栈貌似还卡了递归版拓扑排序）
#include<cstdio>
#include<algorithm>
#include<stack>
#define maxn 200090 using namespace std; int n,r,tot,dfs_clock,scc_cnt,ans=;
int head[maxn],dfn[maxn],low[maxn],size[maxn],scc[maxn];
struct node{
int to,next;
}edge[maxn];
stack<int>s; void add(int x,int y)
{
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
} void tarjan(int x)
{
dfn[x]=low[x]=++dfs_clock;
s.push(x);
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(!dfn[y])
{
tarjan(y);
dfn[x]=min(dfn[x],dfn[y]);
}
else if(!scc[y]) dfn[x]=min(dfn[x],low[y]);
}
if(low[x]==dfn[x])
{
scc_cnt++;
while()
{
int u=s.top();
s.pop();
scc[u]=scc_cnt;
if(x==u) break;
}
}
} int main()
{
freopen("message.in","r",stdin);
freopen("message.out","w",stdout);
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&r),add(i,r);
for(int i=;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=;i<=n;i++)
size[scc[i]]++;
for(int i=;i<=scc_cnt;i++)
if(size[i]!=&&size[i]<ans) ans=size[i];
printf("%d",ans);
return ;
}
message
T3：斗地主
思路：我没玩过斗地主qwq，表示看到题理解游戏规则就用了好久。这貌似是个搜索，不过noip还会考裸的搜索嘛qwq（不过真的考了）。平时搜索能力就很弱，独立写出搜索的情况很少，不过最近有意在练习搜索了qwq，也已经有了自己的理解，对搜索应该还是缺乏训练。这篇写了题解（在这里）。考场上写了n=2/3/4的子任务，就是骗分了。
预计得分：30分
实际得分：20分
（是这样的qwq，n==4的情况我应该是写判断的时候出锅了，暴力都打错了。。。）
#include<algorithm>
#include<cstdio>
#include<cstring> using namespace std; int T,n,no,x,ans=;
int tong[]; void dfs(int now)
{
int cnt=;
for(int i=;i<=;i++)
{// shunzi single
if(tong[i]) cnt++;
else cnt=;
if(cnt>=)
{
tong[i]--,tong[i-]--,tong[i-]--,tong[i-]--;
int k=i-cnt+;
for(int j=i-;j>=k;j--)
tong[j]--,dfs(now+);
for(int j=k;j<=i;j++)
tong[j]++;
}
}
cnt=;
for(int i=;i<=;i++)
{// shunzi double
if(tong[i]>=) cnt++;
else cnt=;
if(cnt>=)
{
tong[i]-=,tong[i-]-=;
int k=i-cnt+;
for(int j=i-;j>=k;j--)
tong[j]-=,dfs(now+);
for(int j=k;j<=i;j++)
tong[j]+=;
}
}
cnt=;
for(int i=;i<=;i++)
{// shunzi third
if(tong[i]>=) cnt++;
else cnt=;
if(cnt>=)
{
tong[i]-=;
int k=i-cnt+;
for(int j=i-;j>=k;j--)
tong[j]-=,dfs(now+);
for(int j=k;j<=i;j++)
tong[j]+=;
}
}
for(int i=;i<=;i++)
{// four with 2
if(tong[i]>=)
{
tong[i]-=;
for(int j=;j<=;j++)
if(tong[j])
{//2 single
tong[j]--;
for(int k=;k<=;k++)
if(tong[k])
{
tong[k]--;
dfs(now+);
tong[k]++;
}
tong[j]++;
}
for(int j=;j<=;j++)
if(tong[j]>=)
{//2 double
tong[j]-=;
for(int k=;k<=;k++)
if(tong[k]>=)
{
tong[k]-=;
dfs(now+);
tong[k]+=;
}
tong[j]+=;
}
dfs(now+);
//three card
tong[i]+=;
}
}
for(int i=;i<=;i++)
{
if(tong[i]>=)
{
tong[i]-=;
for(int j=;j<=;j++)
if(tong[j])
{//three with 1
tong[j]--;
dfs(now+);
tong[j]++;
}
for(int j=;j<=;j++)
if(tong[j]>=)
{//three with 2
tong[j]-=;
dfs(now+);
tong[j]+=;
}
dfs(now+);// 3 single
tong[i]+=;
}
}
if(tong[]==) now++;
else if(tong[]==) now++;
for(int i=;i<=;i++) if(tong[i]) now+=tong[i]>>;
for(int i=;i<=;i++) if(tong[i]) now+=tong[i]&;
ans=min(ans,now);
} int main()
{
scanf("%d%d",&T,&n);
while(T--)
{
for(int i=;i<=n;i++)
{
scanf("%d%d",&x,&no);
if(x==) x=;
else if(x==) x=;
else if(x==) x=;
tong[x]++;
}
dfs();
printf("%d\n",ans);
ans=;
memset(tong,,sizeof(tong));
}
return ;
}
AC-landlord
Day1 预计得分：230
实际得分：200
考场上感觉还是有点松懈，第三题没好好想，暴力还写错了，考场上一定要全身心投入啊qwq
Day2
T1：跳石头
思路：裸的二分答案。“最大距离最小”暗示着我们二分的性质，写check函数也很容易，标准的第一题难度。
预计得分：100分
实际得分：100分
（*Add：写的二分的边界细节好像还是不准，还需要多写一些二分题巩固qwq）
#include<cstdio>
#include<algorithm> using namespace std; int lin,n,m;
int seq[]; bool check(int x)
{
int pre=,cnt=;
for(int i=;i<=n;i++)
{
if(seq[i]-pre<x) cnt++;
else pre=seq[i];
if(cnt>m) return ;
}
return ;
} int main()
{ scanf("%d%d%d",&lin,&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&seq[i]);
seq[n+]=lin;
int l=,r=lin;
while(l<r)
{
int mid=(l+r+)>>;
if(check(mid)) l=mid;
else r=mid-;
}
printf("%d\n",l);
return ;
}
stone
T2：子串
思路：本来dp就弱，字符串也没学多少，二者加起来就mengbier了...读题没有多久就弃疗去看第三题了，结果第三题一打就是几乎三个小时...考前10分钟把k=1的暴力打了，本想苟一苟把k=2的也写上，结果时间也不够了。
预计得分：10分
实际得分：10分
正解：方案数，dp。有经验的dalao可我不是可以轻松推出：设f[i][j][k]表示A串匹配到第i位，B串匹配到第j位，用了k个子串 的方案数。并显然有f[i][j][k]=f[i-1][j-1][k-1]+f[i-1][j-1][k]，但是我们冷静分析会发现这个转移是不靠谱的。
首先是它的正确性：上述转移只有在A[i]==B[j]时才成立，于是我们就遗弃掉了没匹配上的情况。
我们可以再开一个辅助转移数组，s[i][j][k]表示一定用到了当前字符A[i]的方案数，f[i][j][k]表示用或不用当前字符的方案数。
分析s数组的转移：转移的前提是A[i]==B[j]，既然A[i]一定用上了，那么有独自成一串，和与前面组合成一串的两种情况。
那么有s[i][j][k]=f[i-1][j-1][k-1]+s[i-1][j-1][k]。如果不能转移，则为0.（不能忽视的一步！！后面与滚动数组相关）
再分析f数组的转移：可由使用当前字符和不使用当前字符转移过来.
那么有f[i][j][k]=s[i][j][k]+f[i-1][j][k]。
至此我们成功解决了转移的正确性。
但是显然它是会超空间的，dp的优化我们考虑状态和转移，状态没有可优化的地方，那么我们考虑转移。观察到转移的第一维只与上一值有关，我们就可以用滚动数组。然后我是第一次写滚动数组==，其实就是把第一维改成两个量pre和now，转移后交换pre和now，达到i-1的效果。
以及不要忘记赋初值。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=,mod=1e9+;
int n,m,k,dp[][][];
char a[M],b[M];
int main()
{
freopen("substring.in","r",stdin);
freopen("substring.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
scanf("%s",a+);
scanf("%s",b+);
if(k==)
{
int ans=;
for(int i=;i<=n-m+;i++)
{
bool flag=;
for(int j=;j<=m;j++)
if(a[i+j-]!=b[j]){
flag=;break;
}
if(!flag)ans++;
}
ans%=mod;
printf("%d\n",ans);
return ;
}
else if(k==)
{
int ans=;
for(int i=;i<=n-m+;i++)//枚举第一次选的开始位置
{
for(int len=;len<=m-;len++)//枚举第一次选了几个
{
int len1=m-len;
for(int j=i+len;j<=n-len1+;j++)//枚举第二次从哪儿开始选
{
bool flag=;
int p=;
for(int t=i;t<=i+len-;t++)
{
if(a[t]!=b[++p]){
flag=;break;
}
}
if(flag)continue;
for(int t=j;t<=j+len1-;t++)
{
if(a[t]!=b[++p]){
flag=;break;
}
}
if(!flag){
ans++;
//printf("%d %d %d %d\n",i,i+len-1,j,j+len1-1);
}
}
}
}
cout<<ans<<endl;
return ;
}
else
{
for(int i=;i<=k;i++)
dp[][][i]=;
for(int i=;i<=n;i++)
dp[i][][]=;
for(int i=;i<=m;i++)
dp[][i][]=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int t=;t<=k;t++)
{
if(a[i]==b[j])
dp[i][j][t]=((ll)dp[i][j][t]+dp[i-][j-][t]+dp[i-][j][t-])%mod;
else dp[i][j][t]=((ll)dp[i][j][t]+dp[i-][j][t-])%mod;
printf("%d %d %d %d\n",i,j,t,dp[i][j][t]);
}
cout<<dp[n][m][k]<<endl;
return ;
} }
Chemist的30分做法
#include<cstdio>
#include<algorithm> using namespace std;
typedef long long ll; int n,m,k;
ll moder=1e9+,f[][][],s[][][];
char A[],B[]; int main()
{
scanf("%d%d%d",&n,&m,&k);
scanf("%s",A+);
scanf("%s",B+);
int now=,pre=;f[][][]=;
for(int i=;i<=n;i++)
{
f[now][][]=;
for(int j=;j<=m;j++)
for(int q=;q<=k;q++)
{
if(A[i]==B[j]) (s[now][j][q]=s[pre][j-][q]+f[pre][j-][q-])%=moder;
else s[now][j][q]=;
(f[now][j][q]=f[pre][j][q]+s[now][j][q])%=moder;
}
swap(now,pre);
}
printf("%lld",f[pre][m][k]%moder);
return ;
}
substring
T3：运输计划
考场思路：这题我跟它耗了将近三小时qwq.
心路历程如下：（考场上真实记录）
其实感觉m==1的情况还是比较悬的
要是最短路有多条 ，然后最后找到的那条上的最大值恰好比较小 那不就凉了么==然后到3000的数据，开始想n^2算法应该能想出来，后来感觉好像需要n^2logn
dij的复杂度是多少来着？？？nlogn?????如果是nlogn海星 不是就凉了==
dij好像更稳一些，但是我一共也没打过几次dij==
不对，打完dij感觉好像根本不是那么回事 又给删了==
dij求的是单源最短路 复杂度岂不会变成n^3logn？？？
还不如用floyd呢（滑稽）那这样好像要用lca了==
LCA复杂度多少来着？？？好像想出了正解（？？）
但是感觉悬啊
60分差不多吧...
最后当然是非正解了==
预计得分 ：0~100分
实际得分 ：10分
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector> using namespace std;
typedef long long ll; int n,m,tot,t,x,y,z,noww,chang;
ll odd,ans;
int head[],cnt[],d[],f[][];
struct node{
int to,val,next;
}edge[];
queue<int>q;
vector<int>son[]; void add(int x,int y,int z)
{
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
edge[tot].val=z;
} void init()
{
q.push();d[]=;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(d[y]) continue;
d[y]=d[x]+;
f[y][]=x;
for(int j=;j<=t;j++)
f[y][j]=f[f[y][j-]][j-];
q.push(y);
}
}
} int lca(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;i--)
if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=t;i>=;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][];
} bool work(int fa,int x)
{
for(int i=head[fa];i;i=edge[i].next)
if(edge[i].to==x)
{
cnt[i]++;
son[noww].push_back(i);
return ;
}
for(int i=head[fa];i;i=edge[i].next)
{
int y=edge[i].to;
if(y==x)
{
cnt[i]++;
son[noww].push_back(i);
break;
return ;
}
if(work(y,x))
{
cnt[i]++;
son[noww].push_back(i);
return ;
}
}
return ;
} int main()
{
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
scanf("%d%d",&n,&m);
t=log2(n)+;
for(int i=;i<=n-;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
init();
for(int i=;i<=m;i++)
{
scanf("%d%d",&x,&y);
noww=i;
int fa=lca(x,y);
if(fa!=x) work(fa,x);
if(fa!=y) work(fa,y);
}
for(int i=;i<=tot;i+=)
cnt[i]=cnt[i]+cnt[i+];
for(int i=;i<=tot;i+=)
{
ll tmp=cnt[i];
tmp*=edge[i].val;
if(tmp>odd) chang=i,odd=tmp;
}
for(int i=;i<=m;i++)
{
ll tmp=;
for(int j=;j<son[i].size();j++)
if(son[i][j]==chang||son[i][j]==chang+) continue;
else tmp+=edge[son[i][j]].val;
ans=max(ans,tmp);
}
printf("%d",ans);
return ;
}
考场代码 10pts
但是后来努力学习了一下60分做法（开始是想搞到 60分的）
60分做法：50pts n² + 10pts m==1，这些方法就是暴力向上跳。
然后暴力的核心思想：因为这是在树上，所以每个点可以认为有唯一的入度，所以可以预处理出到每个点的边的权值，以及这个点的父亲。
瞎搞vis数组开的3000，数组还越界了...导致有两个骗分点一直输出0.
#include<cstdio>
#include<algorithm>
#define maxn 100090 using namespace std;
typedef long long ll; int n,m,tot;
int head[maxn],d[maxn],fa[maxn],pre[maxn],vis[][],fin[maxn];
struct node{
int to,next,val;
}edge[*maxn];
struct cellur{
int x,y;
}tas[]; ll lmax(ll a,ll b)
{
if(a>b) return a;
else return b;
} void add(int x,int y,int z)
{
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
edge[tot].val=z;
} void dfs(int x)
{
d[x]=d[fa[x]]+;
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(y==fa[x]) continue;
pre[y]=edge[i].val;
fa[y]=x;
dfs(y);
}
} int subw(int pos,int x,int y)
{
int ans=;
if(d[x]<d[y]) swap(x,y);
while(d[x]>d[y])
{
ans+=pre[x];
vis[x][pos]=;
x=fa[x];
}
while(x!=y)
{
ans+=pre[x]+pre[y];
vis[x][pos]=,vis[y][pos]=;
x=fa[x],y=fa[y];
}
return ans;
} void work1()
{
int odd=,ans=;
int x=tas[].x,y=tas[].y;
if(d[x]<d[y]) swap(x,y);
while(d[x]>d[y])
{
ans+=pre[x];
odd=lmax(odd,pre[x]);
x=fa[x];
}
while(x!=y)
{
ans+=pre[x]+pre[y];
odd=lmax(odd,pre[x]);
odd=lmax(odd,pre[y]);
x=fa[x],y=fa[y];
}
printf("%lld",ans-odd);
} void work2()
{
int odd=;
int minn=-;
for(int i=;i<=m;i++) fin[i]=subw(i,tas[i].x,tas[i].y),minn=max(minn,fin[i]);
for(int i=;i<=n;i++)
{
//所有路径只能是pre[i]上的 所以枚举这些边就行
int tmp=;
for(int j=;j<=m;j++)
tmp=max(tmp,fin[j]-pre[i]*vis[i][j]);
//vis数组就是这条边有没有在j这个计划中出现过 只能为0或1
if (minn==-||minn>tmp)minn=tmp;
}
printf("%d",minn);
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n-;i++)
{
int x=,y=,z=;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
for(int i=;i<=m;i++)
scanf("%d%d",&tas[i].x,&tas[i].y);
fa[]=;
dfs();
if(m==)
work1();
else work2();
return ;
}
努力骗到的60pts
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int M=3e5+,MAX=1e7;
typedef long long ll;
int read()
{
int ans=;
char ch=getchar(),last=' ';
while(ch<''||ch>'')
{last=ch;ch=getchar();}
while(ch>=''&&ch<='')
{ans=ans*+ch-'';ch=getchar();}
if(last=='-')ans=-ans;
return ans;
}
int n,m;
ll d[M],ans=1e12;
int num=,head[M];
struct node{
int beg,end,next,w;
}e[M*];
struct Node{
int str,fin,cost;
}P[M];
struct PLAN{
int from,to;
}p[M];
void add(int x,int y,int z)
{
num++;
e[num].beg=x;
e[num].end=y;
e[num].w=z;
e[num].next=head[x];
head[x]=num;
} int size[M],fa[M],son[M],dep[M];
void dfs1(int x)
{
dep[x]=dep[fa[x]]+;
size[x]=;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].end;
if(y==fa[x])continue;
fa[y]=x;
d[y]=(ll)d[x]+e[i].w;
dfs1(y);
size[x]+=size[y];
if(!son[x]||size[son[x]]<size[y])
son[x]=y;
}
} int top[M];
void dfs2(int x,int topfa)
{
top[x]=topfa;
if(!son[x])return;
dfs2(son[x],topfa);
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].end;
if(y==son[x]||y==fa[x])continue;
dfs2(y,y);
}
} int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
return x;
}
bool cmp(Node X,Node Y)
{
return X.cost>Y.cost;
}
int main()
{
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
n=read();m=read();
for(int i=;i<=n-;i++)
{
int x=read(),y=read(),z=read();
add(x,y,z);add(y,x,z);
P[i].str=x;P[i].fin=y;P[i].cost=z;
}
for(int i=;i<=m;i++)
p[i].from=read(),p[i].to=read();
dfs1();
dfs2(,);
if((n<=&&m<=)||m==){
//O(nmlogn)枚举暴力，期望得分：55
for(int i=;i<=num;i+=)//枚举改造了哪个航道
{
int x=e[i].beg,y=e[i].end,A;
if(dep[x]<dep[y])A=x;
else A=y;
ll mx=;
for(int j=;j<=m;j++)
{
int B=p[j].from,E=p[j].to;
int lca=LCA(B,E);
ll tim=d[B]+d[E]-*d[lca];
if((LCA(A,B)==A||LCA(A,E)==E)&&dep[lca]<=dep[A])
tim-=e[i].w;
mx=max(mx,tim);
}
ans=min(ans,mx);
}
cout<<ans<<endl;
}
else{
sort(P+,P+n,cmp);
for(int i=;i<=min(n-,(MAX/m));i++)//枚举改造了哪个航道
{
int x=P[i].str,y=P[i].fin,A;
if(dep[x]<dep[y])A=x;
else A=y;
ll mx=;
for(int j=;j<=m;j++)
{
int B=p[j].from,E=p[j].to;
int lca=LCA(B,E);
ll tim=d[B]+d[E]-*d[lca];
if((LCA(A,B)==A||LCA(A,E)==E)&&dep[lca]<=dep[A])
tim-=P[i].cost;
mx=max(mx,tim);
}
ans=min(ans,mx);
}
cout<<ans<<endl;
}
fclose(stdin);fclose(stdout);
return ;
}
Chemist的70pts骗分法
正解：二分答案+lca+树上差分
一句话题意：给你许多树上的链，要求把树上其中一条边变为0后链权值的最大值最小。
这个题出的二分还是十分隐秘的qwq，（比如zhanggenchen篱落疏疏一径深那题）因为题目要我们求计划最大值最小，所以满足二分单调性。
我们就可以二分这个最终的答案。设这个答案为mid，则所有长度>mid的路径上都至少需要删除一条边，对这些路径求交，最优方案是删去路径中长度最大的边。如果删去这条最长边后最长路径还有大于mid的，那么这个答案不合法。
问题的关键转化为求树上路径交，我们可以使用树上差分（现学的）。
另外这里预处理各个计划的链长我用到的是树上倍增求LCA+dfs。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define maxn 300090
// long long?
using namespace std; int n,m,t,tot,maxlen,l,r,num,ret;
int pre[maxn],head[maxn],d[maxn],f[maxn][],val[maxn],vis[maxn],dis[maxn];
struct node{
int to,next,val;
}edge[maxn*];
struct cellur{
int x,y,len,lca;
}tas[maxn]; void add(int x,int y,int z)
{
edge[++tot].to=y;
edge[tot].next=head[x];
head[x]=tot;
edge[tot].val=z;
} void LCA_prework()
{
queue<int>q;
q.push();d[]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(d[v]) continue;
d[v]=d[u]+;
f[v][]=u;
pre[v]=edge[i].val;
for(int j=;j<=t;j++)
f[v][j]=f[f[v][j-]][j-];
q.push(v);
}
}
} int LCA(int x,int y)
{
if(d[x]>d[y]) swap(x,y);
for(int i=t;i>=;i--)
if(d[f[y][i]]>=d[x]) y=f[y][i];
if(x==y) return x;
for(int i=t;i>=;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][];
} void dfs(int x)
{
vis[x]=;
for(int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if(vis[y]) continue;
dis[y]=dis[x]+edge[i].val;
dfs(y);
}
} void review(int u,int fa)
{
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa) continue;
review(v,u);
val[u]+=val[v];
}
if(val[u]==num&&pre[u]>ret)
ret=pre[u];//记录路径中最长的边
} bool check(int x)
{
memset(val,,sizeof(val));
num=ret=;
for(int i=;i<=m;i++)
{
if(tas[i].len>x)
{
val[tas[i].x]++;
val[tas[i].y]++;
val[tas[i].lca]-=;
num++;
}
}
review(,);
if(maxlen-ret>x) return ;
return ;
} int main()
{
scanf("%d%d",&n,&m);
t=log2(n)+;
for(int i=;i<=n-;i++)
{
int x=,y=,z=;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
for(int i=;i<=m;i++)
scanf("%d%d",&tas[i].x,&tas[i].y);
LCA_prework();
for(int i=;i<=n;i++)
if(!vis[i]) dfs(i);
for(int i=;i<=m;i++)
{
int fa=LCA(tas[i].x,tas[i].y);
tas[i].lca=fa;
tas[i].len=dis[tas[i].x]+dis[tas[i].y]-*dis[fa];
maxlen=max(maxlen,tas[i].len);
}
r=maxlen;
while(l<r)
{
int mid=(l+r)>>;
if(check(mid)) r=mid;
else l=mid+;
//printf("%d %d\n",ret,num);
}
printf("%d",l);
return ;
}
（但是不开longlong好像也没关系的样子...）
Day2 预计得分：100+10+0~100=110~210
实际得分：100+10+10=120
感觉考场上不能像我今天一样再孤注一掷写T3正解了吧...，拿个稳妥的暴力分也是好的呀...。所以今天的时间分配出现了很大问题，第二题虽然我dp很不好应该至少还能加上20分k=2的情况吧，实在布星T3把所以m==1的情况都打出来，顺便再打个n==100的情况也比我现在的结果强啊qwq。考试策略和技巧还有待改善。
扯些别的：
现在感觉学习了那么多算法，目的当然是尽量在考场上打出正解。但是事实是，T2正解都很难想全，T3正解就更难了。OI赛制中暴力分，部分分还是王道。学习那么多算法，也是让我们在考场上掌握更多优雅的暴力方法，得到更多的分啊。比如ChemistDay2T3打了一个大概是树剖的东西吧，搞到了60pts(?，而我不会树剖，更不会从树的链角度出发分析==
然后感觉现在基础并不牢固==一些算法掌握的也不牢==比如滚动数组优化当初学长讲了但没写，搜索缺少方法，动规更是一塌糊涂==。对照学长给的noip知识表好像没有多少算法敢说自己掌握的特别牢==，比如树上倍增/差分。
还有一些实用技巧也并不会==，比如生成数据手打就有时候不会，（已加入todolist），有的算法复杂度不确定等等==