题解：

个人认为这道题很不友好，因为思路不清晰调了好久。

这道题实际上就是求一棵树的带权重心，很显然一个点越远离带权重心，权值和就会越大。

那么我们先说一下暴力的思路，假设当前点为x，如果存在一个点y，权值和小于x，那么就向y这个方向转移，直到与x相邻的点中没有权值和比x小的，那么此时的x就是答案。

这种做法是$O(n^{2})$的，显然过不了所有的数据，考虑优化。

考虑动态点分，假设我们每次都从根节点x来搜索答案，那么如果当前点不是答案，那么与当前点相邻的点中，一定存在答案比当前点小的点y，而且这个点若存在就是唯一存在。

那么我们找到y所在子树的重心z，继续从z开始做就好。

由于点分树的深度最深为logn，所以这种算法有复杂度保证。

注意：这道题普通的RMQ求LCA过不了，会超时，要用查询复杂度为$O(1)$的欧拉序LCA。

1 //Never forget why you start  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 #include
          
            8 #define inf (2147483647) 9 using namespace std; 10 typedef long long lol; 11 int n,m,lim; 12 struct node{ 13 int next,to; 14 lol dis; 15 }edge[200005]; 16 int head[100005],size; 17 void putin(int from,int to,lol dis){ 18 size++; 19 edge[size].next=head[from]; 20 edge[size].to=to; 21 edge[size].dis=dis; 22 head[from]=size; 23 } 24 int place[100005],dfscnt,st[200005][21],dfn,o[100005]; 25 lol dis[100005]; 26 void dfs1(int r,int father){ 27 int i,s=++dfn; 28 st[++dfscnt][0]=s; 29 o[s]=r; 30 place[r]=dfscnt; 31 for(i=head[r];i!=-1;i=edge[i].next){ 32 int y=edge[i].to; 33 if(y!=father){ 34 dis[y]=dis[r]+edge[i].dis; 35 dfs1(y,r); 36 st[++dfscnt][0]=s; 37 } 38 } 39 } 40 void make(){ 41 lim=log(n*2)/log(2); 42 for(int i=1;i<=lim;i++) 43 for(int j=1;j<=dfscnt;j++) 44 if(j+(1<
           
            <=dfscnt) 45 st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]); 46 } 47 int LCA(int x,int y){ 48 if(place[x]>place[y])swap(x,y); 49 int lg=log(place[y]-place[x]+1)/log(2); 50 return o[min(st[place[x]][lg],st[place[y]-(1<
            
             d[r])root=r; 70 } 71 void buildtree(int r,int father){ 72 int i,all=tot; 73 vis[r]=1;ff[r]=father; 74 for(i=head[r];i!=-1;i=edge[i].next){ 75 int y=edge[i].to; 76 if(!vis[y]){ 77 if(cnt[y]>cnt[r])cnt[y]=all-cnt[r];tot=cnt[y]; 78 root=0;getroot(y,r);buildtree(root,r); 79 } 80 } 81 } 82 lol p[100005][2]; 83 void insert(int x,int v){ 84 int i; 85 for(i=x;ff[i];i=ff[i]){ 86 lol len=dist(x,ff[i]); 87 p[i][1]+=len*v; 88 p[ff[i]][0]+=len*v; 89 } 90 for(i=x;i;i=ff[i])cnt[i]+=v; 91 } 92 lol query(int x){ 93 int i; 94 lol ans=p[x][0]; 95 for(i=x;ff[i];i=ff[i]){ 96 lol len=dist(x,ff[i]); 97 ans+=p[ff[i]][0]; 98 ans+=len*(cnt[ff[i]]-cnt[i]); 99 ans-=p[i][1];100 }101 return ans;102 }103 lol find(int r,lol ans){104 int i,to=0;105 vis[r]=1;106 for(i=head[r];i!=-1;i=edge[i].next){107 int y=edge[i].to;108 lol tmp=query(y);109 if(tmp
             
              '9'){ if(i=='-')f=-1;i=getchar();}126 while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}127 return ans*f;128 }129 int main(){130 freopen("zjoi15_tree.in","r",stdin);131 freopen("zjoi15_tree.out","w",stdout);132 clean();133 int i,j;134 n=read();m=read();135 for(i=1;i