@[Phantom2009](/user/580036) 不用 vector，用链式前向星？
by sto_5k_orz @ 2023-06-13 19:20:52
交换一下数组的两维？
by gk4000plus @ 2023-06-13 19:31:35
加fread可以有明显的速度提升
by gk4000plus @ 2023-06-13 19:38:46
把(i)++改++(i)
by c20101224 @ 2023-06-13 19:56:17
不用换数组了，加上fread然后改结构体存边（代替vector)可能能过
by gk4000plus @ 2023-06-13 20:02:20
现在明显非常快了
by gk4000plus @ 2023-06-13 20:14:20
```cpp
#include<iostream>
#include <cstring>
#include <vector>
using std::pair;
using std::vector;
using std::cin;
using std::cout;
typedef pair<signed, signed> pii;
typedef pair<pair<signed, signed>, signed> ppii;
void swap(int &x, int &y) {
int tmp = x;
x = y;
y = tmp;
}
signed abs(int &x) {
return x > 0 ? x : -x;
}
signed max(const int x, const int y) {
return x > y ? x : y;
}
signed lca[300001][18],d[300001],f[300001],ch[300001],res[300001][18];
vector<pii>p[300001];
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline void dfs(int now,int fa,int ls){
lca[now][0] = f[now] = fa;d[now] = d[fa]+1;res[now][0] = ls;
int len = (int)p[now].size();
for(int i =0 ;i<len;++i){
if(p[now][i].first==fa)continue;
dfs(p[now][i].first,now,p[now][i].second);
}return;
}inline pair<signed,signed> lcaa(int x,int y){
if(d[x]<d[y])swap(x,y);
int dis = abs(d[x]-d[y]),sum =0 ;
for(int i =0;dis;++i,dis>>=1){
if(dis&1)sum+=res[x][i],x = lca[x][i];
}if(x == y)return pii(x,sum);
for(int i = 17;i>=0;--i){
if(lca[x][i] != lca[y][i])sum+=res[x][i]+res[y][i],x = lca[x][i],y = lca[y][i];
}return {lca[x][0],sum+res[x][0]+res[y][0]};
}inline pair<signed,signed> dis(int x,int y){
int l = lcaa(x,y).first;
int dis = abs(d[x]-d[l]);int ans =0;
for(int i =0;dis;++i,dis>>=1) {
if(dis&1)ans+=res[x][i],x= lca[x][i];
}
dis = abs(d[y]-d[l]);
for(int i =0;dis;++i,dis>>=1) {
if(dis&1)ans+=res[y][i],y= lca[y][i];
}
return pii(l, ans);
}
inline void dfs2(int now){
int len = (int)p[now].size();
for(int i =0;i<len;++i){
if(p[now][i].first == f[now])continue;
dfs2(p[now][i].first);
ch[now]+=ch[p[now][i].first];
}
}vector<pair<pair<signed,signed>,signed> >edge;
signed mx;
struct Node{
signed x,y,l,sum;
};vector<Node>query;
signed querylen;
signed edgelen;
inline bool check(int x){
//cout << x << endl;
memset(ch,0,sizeof(ch));
int tot = 0,c = 0;
for(int i =0;i<querylen;++i){
if(query[i].sum>x){
// cout << query[i].x << " " << query[i].y << " " << query[i].sum << " " <<query[i].l<< endl;
ch[query[i].x]+=1,ch[query[i].y]+=1;
ch[query[i].l]-=2;
c= max(c,query[i].sum);tot++;
}
}if(mx+x<c)return 0;
//cout << tot << endl;
//for(int i = 1;i<=n;++i)cout << ch[i] << " ";cout << endl;
dfs2(1);
//for(int i =1;i<=n;++i)cout << ch[i] << " ";cout << endl;
for(int i =0;i<edgelen;++i){
int xx = edge[i].first.first,y = edge[i].first.second;
int p = xx;
if(d[xx]<d[y])p= y;
if(ch[p] == tot){
// cout << xx << " " << y << endl;
if(edge[i].second>=c-x)return 1;
}
}return 0;
}
inline signed read() {
char c = getc();
int num = 0;
while (c < '0' || c > '9') {
c = getc();
}
while (c >= '0' && c <= '9') {
num = (num << 1) + (num << 3) + (c ^ 48);
c = getc();
}
return num;
}
signed main(){
// freopen("P2680_1.in", "r", stdin);
int n = read(), m = read();
for(int i = 1;i<n;++i){
int a = read(), b = read(), c = read();
p[a].push_back(pii(b, c)); p[b].push_back(pii(a, c));
edge.push_back(ppii(pii(a, b),c));
mx = max(mx,c);
}
edgelen = (int)edge.size();
dfs(1,1,0);
for(int i = 1; i < 18; ++i) {
int now;
for (now = 1; now <= n - 8; now += 8) {
lca[now][i] = lca[lca[now][i-1]][i-1];
res[now][i] = res[now][i-1]+res[lca[now][i-1]][i-1];
lca[now + 1][i] = lca[lca[now + 1][i-1]][i-1];
res[now + 1][i] = res[now + 1][i-1]+res[lca[now + 1][i-1]][i-1];
lca[now + 2][i] = lca[lca[now + 2][i-1]][i-1];
res[now + 2][i] = res[now + 2][i-1]+res[lca[now + 2][i-1]][i-1];
lca[now + 3][i] = lca[lca[now + 3][i-1]][i-1];
res[now + 3][i] = res[now + 3][i-1]+res[lca[now + 3][i-1]][i-1];
lca[now + 4][i] = lca[lca[now + 4][i-1]][i-1];
res[now + 4][i] = res[now + 4][i-1]+res[lca[now + 4][i-1]][i-1];
lca[now + 5][i] = lca[lca[now + 5][i-1]][i-1];
res[now + 5][i] = res[now + 5][i-1]+res[lca[now + 5][i-1]][i-1];
lca[now + 6][i] = lca[lca[now + 6][i-1]][i-1];
res[now + 6][i] = res[now + 6][i-1]+res[lca[now + 6][i-1]][i-1];
lca[now + 7][i] = lca[lca[now + 7][i-1]][i-1];
res[now + 7][i] = res[now + 7][i-1]+res[lca[now + 7][i-1]][i-1];
}
for (; now <= n; ++now) {
lca[now][i] = lca[lca[now][i-1]][i-1];
res[now][i] = res[now][i-1]+res[lca[now][i-1]][i-1];
}
}
for(int i = 1;i<=m;++i){
int a = read(), b = read();pair<signed,signed>e = lcaa(a,b);
query.push_back((Node){a,b,e.first,e.second});
}
querylen = (int)query.size();
int l = 0,r = 3e8;
while (l < r){
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}printf("%d\n", l);
return 0;
}
```
@[Phantom2009](/user/580036)
极限了 累了
by dlsnb @ 2023-06-13 20:27:03
看起来和我差不多啊，但是我跑100ms（）
预估是 vector 存图自带 2 倍常数的问题罢
by liangbowen @ 2023-06-13 20:27:38
```cpp
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
uint n,m;
constexpr int L = 1<<20|1;
char buf[L],*S,*T,pbuf[L],*pp = pbuf;
#define getchar() ((S == T && (S = buf) == (T = buf+fread(buf,1,L,stdin)))?EOF:*S++)
inline void pf(const char &c){if(pp-pbuf == L) fwrite(pbuf,1,L,stdout),pp = pbuf;*pp++ = c;}
inline void rd(int &x){
x = 0;char ch = getchar();
while(ch < '0') ch = getchar();
while(ch >= '0') x = x*10+(ch^'0'),ch = getchar();
}
inline void Rd(uint &x){
x = 0;char ch = getchar();
while(ch < '0') ch = getchar();
while(ch >= '0') x = x*10+(ch^'0'),ch = getchar();
}
inline void wt(int x){
static int st[30],tp;
do st[++tp] = x%10,x /= 10;while(x);
while(tp) pf(st[tp--]|'0');
}
void swap(uint &x, uint &y) {
x^=y;
y^=x;
x^=y;
}
signed abs(int &x) {
return x > 0 ? x : -x;
}
signed max(const int x, const int y) {
return x > y ? x : y;
}
uint lca[300005][20],f[300005],ch[300005],res[300005][20];
int d[300005];
struct edge{
uint to,nxt;
int w;
}e[(int)6e5+10];
uint head[(int)3e5+10],idx;
void add(uint i,uint j,int w){
e[++idx].to=j;
e[idx].nxt=head[i];
head[i]=idx;
e[idx].w=w;
}
inline void dfs(int now,int fa,int ls){
lca[now][0] = f[now] = fa;d[now] = d[fa]+1;res[now][0] = ls;
for(register uint i = 1;i<18;i++)lca[now][i] = lca[lca[now][i-1]][i-1],res[now][i] = res[now][i-1]+res[lca[now][i-1]][i-1];
for(register uint i =head[now] ;i;i=e[i].nxt){
if(e[i].to==fa)continue;
dfs(e[i].to,now,e[i].w);
}return;
}inline pair<int,int> lcaa(int x,int y){
if(d[x]<d[y])swap(x,y);
int dis = abs(d[x]-d[y]),sum =0 ;
for(register uint i =0;i<18,dis;i++,dis>>=1){
if(dis&1)sum+=res[x][i],x = lca[x][i];
}if(x == y)return {x,sum};
for(register int i = 17;i>=0;i--){
if(lca[x][i] != lca[y][i])sum+=res[x][i]+res[y][i],x = lca[x][i],y = lca[y][i];
}return {lca[x][0],sum+res[x][0]+res[y][0]};
}inline pair<int,int> dis(int x,int y){
int l = lcaa(x,y).first;
int dis = abs(d[x]-d[l]);int ans =0;
for(register uint i =0;dis;i++,dis>>=1)if(dis&1)ans+=res[x][i],x= lca[x][i];
dis = abs(d[y]-d[l]);
for(register uint i =0;dis;i++,dis>>=1)if(dis&1)ans+=res[y][i],y= lca[y][i];
return {l,ans};
}
inline void dfs2(int now){
for(register uint i =head[now];i;i=e[i].nxt){
if(e[i].to == f[now])continue;
dfs2(e[i].to);
ch[now]+=ch[e[i].to];
}return;
}
struct Edge{
uint x,y;
int w;
}E[(int)3e5+10];
int mx =0;
struct node{
int x,y,l,sum;
}query[(int)3e5+10];
bool check(int x){
//cout << x << endl;
memset(ch,0,sizeof(ch));
int tot = 0,c = 0;
for(register int i =1;i<=m;i++){
if(query[i].sum>x){
// cout << query[i].x << " " << query[i].y << " " << query[i].sum << " " <<query[i].l<< endl;
ch[query[i].x]+=1,ch[query[i].y]+=1;
ch[query[i].l]-=2;
c= max(c,query[i].sum);tot++;
}
}if(mx+x<c)return 0;
dfs2(1);
for(register uint i=1;i<n;i++){
uint xx = E[i].x,y = E[i].y;
uint p = xx;
if(d[xx]<d[y])p= y;
if(ch[p] == tot){
if(E[i].w>=c-x)return 1;
}
}return 0;
}
signed main(){
Rd(n);Rd(m);
for(register uint i = 1;i<n;i++){
uint a,b;int c;Rd(a);Rd(b);rd(c);
add(a,b,c);add(b,a,c);
E[i]={a,b,c};mx=max(mx,c);
}dfs(1,1,0);
for(register uint i = 1;i<=m;i++){
uint a,b;Rd(a);Rd(b);pair<int,int>e = lcaa(a,b);
query[i]={a,b,e.first,e.second};
}register uint l = 0,r = 3e8;
while(l<r){
int mid = l+r>>1;
if(check(mid))r = mid;
else l = mid+1;
}wt(l),pf('\n');
fwrite(pbuf,1,pp-pbuf,stdout);
return 0;
}
```
可以跑到1200左右，再卡就有点浪费时间了，建议学习小常数代码
by gk4000plus @ 2023-06-13 20:28:40
感谢所有回复的大佬。
by SnowTrace @ 2023-06-13 20:44:26