竹子听

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 10000

#define max(x,y) x>=y?x:y

int n,M,fa[maxn],top[maxn],siz[maxn],hchild[maxn],deep[maxn],id[maxn],iid[maxn],tree[maxn<<2];

int pre[maxn],to[maxn],next[maxn],weight[maxn],wei[maxn],num=0,tip=0;

void clear()

{

memset(fa,0,sizeof(int));memset(top,0,sizeof(int));memset(siz,0,sizeof(int));

memset(deep,0,sizeof(int));memset(hchild,0,sizeof(int));memset(id,0,sizeof(int));

memset(iid,0,sizeof(int));memset(weight,0,sizeof(int));memset(wei,0,sizeof(int)); 

memset(tree,0,sizeof(int));memset(pre,0,sizeof(int));memset(to,0,sizeof(int));

memset(next,0,sizeof(int));

}

void addedge(int x,int y,int z)

{num++; next[num]=pre[x],pre[x]=num,to[num]=y,weight[num]=z;}

void swap(int &x,int &y){int c=x;x=y,y=c;}

void updata()

{

for(int i=M-1;i>=1;i--) tree[i]=max(tree[i<<1],tree[i<<1|1]);

}

int query(int x,int y)

{

int ans=0;

x+=M,y+=M;

x--,y++;

while(1)

{

if(x%2==0)ans=max(ans,tree[x+1]);

if(y%2==1)ans=max(ans,tree[y-1]);

x<<=1,y<<=1; 

if(x+1==y) break;

}

return ans;

}

void dfs1(int father,int now,int depth)

{

int p=pre[now];

deep[now]=depth;

fa[now]=father;

//if(!p){siz[now]=1;return;} 

while(p)

{

if(to[p]==father) {p=next[p];continue;}

dfs1(now,to[p],depth+1);

siz[now]+=siz[to[p]];

if(siz[to[p]]>siz[hchild[now]]) hchild[now]=to[p],wei[now]=weight[p];

p=next[p];

}

if(!siz[now]) siz[now]=1;

}

void dfs2(int father,int now,int tp,int weig)

{

int p=pre[now];

top[now]=tp;

id[now]=tip;

tree[tip+M]=weig,tip++;

if(!p) return;

if(hchild[now]) dfs2(now,hchild[now],tp,wei[now]);

while(p)

{

if(to[p]==father||to[p]==hchild[now]) {p=next[p];continue;}

dfs2(now,to[p],to[p],weight[p]);

p=next[p];

}

}

int ask_max(int u,int v)

{

int t1=top[u],t2=top[v],ans=0;

while(t1!=t2)

{

if(deep[u]<deep[v]){swap(u,v),swap(t1,t2);}

ans=max(ans,query(id[u],id[t1]));

u=fa[top[u]],t1=top[u];

}

if(u==v) return ans;

if(deep[u]<deep[v]){swap(u,v),swap(t1,t2);}

ans=max(ans,query(id[hchild[u]],id[v]));

return ans;

}

int main()

{

int m,temp1,temp2,temp3;

clear();

scanf("%d%d",&n,&m);

for(M=1;M<n;M<<=1);

for(int i=1;i<=n-1;i++)

{

scanf("%d%d%d",&temp1,&temp2,&temp3);

addedge(temp1,temp2,temp3);

addedge(temp2,temp1,temp3);

}

dfs1(1,1,1);

dfs2(1,1,1,0);

updata();

for(int i=1;i<=m;i++)

{

scanf("%d%d",&temp1,&temp2);

printf("%d\n",query(temp1,temp2));

}

}

12 5

1 2 1

2 8 2

2 6 14

8 11 5

8 10 2

1 3 1

3 4 1

3 5 1

4 7 8

4 9 13

5 12 2