题目链接点这里
终于把去年省热身赛的这题补了，，，好久没写这么复杂的题了，，写了2个小时，，调了一个小时bug。。总共花3小时，，，还是太菜了。。
，，大概，用ST表求任意2点间的距离
线段树查询任意一个区间的最大路径。。。。。
#include<algorithm> #include<iostream> #include<cstring> #include<queue> #include<cmath> #include<cstdio> using namespace std; #define mem(x,y) memset(x,y,sizeof(x)) #define FIN freopen("input.txt","r",stdin) #define fuck(x) cout<<x<<endl const int MX=111111; #define INF 0x3f3f3f3f #define lson l,m,rt<<1 typedef long long LL; typedef pair<int,int> PII; #define rson m+1,r,rt<<1|1 #define lson l,m,rt<<1 int n,m; int head[MX],cnt; struct Edge { int nxt,to,dis; } E[2*MX]; void edge_init() { mem(head,-1); cnt=0; } void edge_add(int u,int v,int dis) { E[cnt].nxt=head[u]; E[cnt].to=v; E[cnt].dis=dis; head[u]=cnt++; } int w[20][2*MX],n_cnt;//ST表 int dis[MX];//每个点到根节点的距离 int p[MX];//每个节点出现的最先编号 int dep[MX];//每个节点的深度 void dfs(int u,int d,int fa,int dist) { p[u]=n_cnt; w[0][n_cnt++]=u; dep[u]=d; dis[u]=dist; for(int i=head[u]; ~i; i=E[i].nxt) { int v=E[i].to; if(v==fa)continue; dfs(v,d+1,u,dist+E[i].dis); w[0][n_cnt++]=u; } } void ST_init() { for(int i=1; (1<<i)<=n_cnt; i++) { for(int j=0; j+(1<<i)<=n_cnt; j++) { if(dep[w[i-1][j]]<=dep[w[i-1][j+(1<<(i-1))]]) w[i][j]=w[i-1][j]; else w[i][j]=w[i-1][j+(1<<(i-1))]; } } } int ST_query(int u,int v) { int l=p[u],r=p[v]; if(l>r) swap(l,r); int len=r-l+1,i; for(i=0; (1<<i)<=len; i++); i--; int fa; if(dep[w[i][l]]>dep[w[i][r-(1<<i)+1]]) fa=w[i][r-(1<<i)+1]; else fa=w[i][l]; return dis[u]+dis[v]-2*dis[fa]; } //线段树 int sum[MX<<2][2]; PII bin(PII a,PII b) { // cout<<a.first<<" "<<a.second<<" "<<b.first<<" "<<b.second<<endl; PII c; int x1,x2,x3,x4,x5,x6; if(a.second!=-1&&b.second!=-1) x4=ST_query(a.second,b.second); else x4=-INF; x3=ST_query(a.first,b.first); if(a.second==-1)x1=x5=-INF; else { x1=ST_query(a.first,a.second); x5=ST_query(a.second,b.first); } if(b.second==-1)x2=x6=-INF; else { x2=ST_query(b.first,b.second); x6=ST_query(a.first,b.second); } int mx=max(x1,x2); mx=max(mx,x3); mx=max(mx,x4); mx=max(mx,x5); mx=max(mx,x6); if(mx==x1) c.first=a.first,c.second=a.second; else if(mx==x2) c.first=b.first,c.second=b.second; else if(mx==x3) c.first=a.first,c.second=b.first; else if(mx==x4) c.first=a.second,c.second=b.second; else if(mx==x5) c.first=a.second,c.second=b.first; else if(mx==x6) c.first=a.first,c.second=b.second; return c; } void build(int l,int r,int rt) { if(l==r) { sum[rt][0]=l; sum[rt][1]=-1; return ; } int m=(l+r)>>1; build(lson); build(rson); PII a=bin(PII(sum[rt<<1][0],sum[rt<<1][1]),PII(sum[rt<<1|1][0],sum[rt<<1|1][1])); sum[rt][0]=a.first; sum[rt][1]=a.second; } PII query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return PII(sum[rt][0],sum[rt][1]); } int m=(l+r)>>1; PII a,b; if(m>=L) a=query(L,R,lson); if(m+1<=R) b=query(L,R,rson); if(!a.first)return b; if(!b.first)return a; return bin(a,b); } int main() { FIN; while(cin>>n>>m) { edge_init(); for(int i=1; i<n; i++) { int u,v,dis; scanf("%d%d%d",&u,&v,&dis); edge_add(u,v,dis); edge_add(v,u,dis); } n_cnt=0; dfs(1,1,-1,0); //fuck(n_cnt); //for(int i=0; i<n_cnt; i++)printf("%d ",w[0][i]); ST_init(); build(1,n,1); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); PII a=query(u,v,1,n,1); if(u>v)swap(u,v); // cout<<a.first<<" "<<a.second<<endl; printf("%d\n",ST_query(a.first,a.second)); } } return 0; }