Link：Problem
大意是给一颗代权树。Q个询问。每个询问是两个节点。
让你回答这两个节点之间路径上的最长边和最短边。
跟PKU月赛的某题有点像。
使用离线算法类tarjan算法。
在并查集中对每个节点维护一个到父亲（并查集中的父亲）的路径上最长和最短的边。。
那么在路径压缩的时候也可以顺便合并。。
在求出两个节点之间的lca之后。。等dfs回到了这个lca。。就有充分的信息了。。
可以很方便的计算答案
PS我太依赖stl了。。这样下去怎么行
Code：
#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1;
const int maxn=100000;int n;
const int maxm=maxn;int m;
struct edge
{
int t,c;
edge(int _t,int _c):t(_t),c(_c){}
};
struct queryLca
{
int t,n;
queryLca(int _t,int _n):t(_t),n(_n){}
};
struct query
{
int a,b,n;
query(int _a,int _b,int _n):a(_a),b(_b),n(_n){}
};
struct info
{
int Min,Max;
info():Min(inf),Max(-inf){}
info(int v):Min(v),Max(v){}
void print() const{cout<<"{"<<Min<<","<<Max<<"}";}
void Merge(const info& o)
{
//print();cout<<" + ";o.print();cout<<endl;
Min=min(Min,o.Min);
Max=max(Max,o.Max);
}
};
vector<edge> E[maxn];
vector<queryLca> Lca[maxn];
vector<query> Query[maxn];
typedef vector<edge>::iterator eit;
typedef vector<queryLca>::iterator lit;
typedef vector<query>::iterator qit;
info Ans[maxm];
void add_edge(int s,int t,int c)
{
E[s].pb(edge(t,c));
E[t].pb(edge(s,c));
}
void add_lca(int s,int t,int n)
{
Lca[s].pb(queryLca(t,n));
Lca[t].pb(queryLca(s,n));
}
info P[maxn];
int F[maxn];
void set()
{
rep(i,n) F[i]=i;
}
int find(int x)
{
int tmp=F[x];
if(F[x]!=x)
F[x]=find(F[x]),P[x].Merge(P[tmp]);
return F[x];
}
void Union(int i,int j,int c)
{
F[j]=i;
P[j]=info(c);
}
bool vis[maxn]={0};
void dfs(int x)
{
vis[x]=true;//cout<<x<<endl;
for(eit i=E[x].begin();i!=E[x].end();i++)if(!vis[i->t])
dfs(i->t),Union(x,i->t,i->c);
for(lit i=Lca[x].begin();i!=Lca[x].end();i++)
{
if(vis[i->t])
{
Query[find(i->t)].pb(query(x,i->t,i->n));
//cout<<find(i->t)<<" "<<x<<" "<<i->t<<endl;
}
}
for(qit i=Query[x].begin();i!=Query[x].end();i++)
{
find(i->a);find(i->b);
info&x=Ans[i->n];
x=P[i->a];x.Merge(P[i->b]);
}
}
void init()
{
scanf("%d",&n);int s,t,c;
set();
for(int i=0;i<n-1;i++)
{
scanf("%d %d %d",&s,&t,&c);
add_edge(s-1,t-1,c);
}
scanf("%d",&m);int a,b;
for(int i=0;i<m;i++)
{
scanf("%d %d",&a,&b);
add_lca(a-1,b-1,i);
}
}
void solve()
{
dfs(0);
for(int i=0;i<m;i++)
printf("%d %dn",Ans[i].Min,Ans[i].Max);
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
init();
solve();
}
本高亮代码使用codeHl生成，
话说我3点半了闲着无聊居然开始刷题了。。
。。。这是编程题么。。明明是BT纯高等数学题。。