提交时间:2022-07-13 12:14:12
运行 ID: 51609
#include <bits/stdc++.h> using namespace std; int n,m,edge[2005],cnt,u,v,w; struct node{ int fa,etf,r; vector<int> son; }a[2005]; inline void find(int u,int v){ while(a[u].r>a[v].r) edge[++cnt]=a[u].etf,u=a[u].fa; while(a[v].r>a[u].r) edge[++cnt]=a[v].etf,v=a[v].fa; while(u^v) edge[++cnt]=a[u].etf,edge[++cnt]=a[v].etf,u=a[u].fa,v=a[v].fa; } int main(){ cin>>n; for(int i=1;i<n;i++) cin>>u>>v>>w,a[v].fa=u,a[v].etf=w,a[u].son.push_back(v),a[v].r=a[u].r+1; cin>>m; while(m--){ cin>>u>>v>>w; find(u,v); sort(edge+1,edge+cnt+1); if((!cnt)||w<edge[1]) printf("%d\n",w); else for(int i=cnt;i;i--){ if(w>=edge[i]){ int num=1; while(i&&edge[i]==edge[i-1]) num++,i--; if(num&1){ printf("%d\n",w-edge[i]); break; } } if(i==1) printf("%d\n",w); } cnt=0; } return 0; }