记录编号	310189	评测结果	AAAAAAAAAA
题目名称	距离	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	4.070 s
提交时间	2016-09-21 19:31:03	内存使用	687.44 MiB

#include<fstream>
#include<vector>
using namespace std;
int f[10001],ances[10001],vis[10001],lca[10001][10001],dist[10001],v[10001][10001]={0};
vector<int>a[10001];
vector<int>q[10001];
/*inline int GetInt(FILE *fin)
{
	int num = 0,flag = 0;
	char ch;
	ch = fgetc(fin);
	while(' ' == ch || '\n' == ch)
		ch = fgetc(fin);
	if ('-' == ch)
	{
		flag = 1;
		ch = fgetc(fin);
	}
	while('0' <= ch && ch <= '9')
	{
		num = (num << 3) + (num << 1) + ch - '0';
		ch = fgetc(fin);
	}
	if (flag)
		return -num;
	else
		return num;
}*/
void memset(int n){
    for(int i=1;i<=n;i++){
        f[i]=i;
        ances[i]=i;
        vis[i]=0;
        dist[i]=0;
        v[i][i]=0;
    }}
int findf(int x){
    if(f[x]!=x){
        f[x]=findf(f[x]);}
    return f[x];}
void merge(int x,int y){
    int xx=findf(x);
    int yy=findf(y);
    if(xx!=yy){
        f[xx]=yy;}}
void tarjan(int u){
    vis[u]=1;
    f[u]=u;
    ances[u]=u;
    int temp=a[u].size();
    for(int i=0;i<temp;i++){
        if(vis[a[u][i]]==0){
			dist[a[u][i]]=dist[u]+v[u][a[u][i]];
        tarjan(a[u][i]);
        merge(a[u][i],u);
		ances[findf(u)]=u;
		}}
    temp=q[u].size();
    for(int i=0;i<temp;i++){
        if(vis[q[u][i]]==1){
            lca[u][q[u][i]]=ances[findf(q[u][i])];
            lca[q[u][i]][u]=ances[findf(q[u][i])];
        }}}
int main(){
    ifstream fin("distance.in");
    ofstream fout("distance.out");
    int n,m,x[20001]={0},y[20001]={0},i,j,s,t;
    fin>>n>>m;
	memset(n);
    for(i=0;i<n-1;i++){
        fin>>j>>s>>t;
        a[j].push_back(s);
        a[s].push_back(j);
        v[j][s]=t;
        v[s][j]=t;}
    for(i=0;i<m;i++){
		fin>>x[i]>>y[i];
        q[x[i]].push_back(y[i]);
        q[y[i]].push_back(x[i]);
    }
    tarjan(1);
    for(i=0;i<m;i++){
        fout<<dist[x[i]]+dist[y[i]]-(dist[lca[x[i]][y[i]]]*2)<<endl;}
    return 0;
}