e=E[e].next){
int v=E[e].v;
if(v==pre) continue;
temp=depth[v]+1;
if(temp>max1[u]){
max3[u]=max2[u];v3[u]=v2[u];
max2[u]=max1[u];v2[u]=v1[u];
max1[u]=temp;
v1[u]=v;
}else if(temp>max2[u]){
max3[u]=max2[u];v3[u]=v2[u];
max2[u]=temp;
v2[u]=v;
}else if(temp>max3[u]){
max3[u]=temp;
v3[u]=v;
}
}
temp=0;
if(pre){
if(v1[pre]!=u) temp=max1[pre]+1;
else if(v2[pre]!=u) temp=max2[pre]+1;
else temp=max3[pre]+1;
if(temp>max1[u]){
max3[u]=max2[u];v3[u]=v2[u];
max2[u]=max1[u];v2[u]=v1[u];
max1[u]=temp;
v1[u]=pre;
}else if(temp>max2[u]){
max3[u]=max2[u];v3[u]=v2[u];
max2[u]=temp;
v2[u]=pre;
}else if(temp>max3[u]){
max3[u]=temp;
v3[u]=pre;
}
int umax1=max1[u];
int umax2=max2[u];
int premax1=max1[pre];
int premax2=max2[pre];
if(v1[u]==pre) umax1=max3[u];
else if(v2[u]==pre) umax2=max3[u];
if(v1[pre]==u) premax1=max3[pre];
else if(v2[pre]==u) premax2=max3[pre];
temp=max(umax1+umax2,premax1+premax2)*prew;
if(temp
#include
#include
#include
#include
#include
#include
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const int INF=0x3f3f3f3f;
struct Edge{
int v,next;
int id;
int w;
}E[100010*2];
int head[100010],size;
void addedge(int u,int v,int w,int id){
E[size].id=id;
E[size].v=v;
E[size].w=w;
E[size].next=head[u];
head[u]=size++;
}
void initedge(){
size = 0 ;
memset(head, -1,sizeof head);
}
int len,root;
int p[100010];
int q[100010];
int man[100010];
void dfs0(int u,int deep,int pre){
if(deep>len){
len=deep;
root=u;
}
for(int e=head[u] ; e!=-1 ; e=E[e].next){
int v=E[e].v;
if(v==pre) continue;
dfs0(v,deep+1,u);
}
}
int dep[100010];
void dfs(int u,int pre){
q[u] = pre;
dep[u] = dep[pre] + 1;
for(int e=head[u] ; e!=-1 ; e=E[e].next){
int v=E[e].v;
if(v==pre) continue;
dfs(v,u);
}
}
int ans,ansid;
void solve(int u,int pre){
for(int e=head[u] ; e!=-1 ; e=E[e].next){
int v=E[e].v;
int w=E[e].w;
int id=E[e].id;
if(v==pre) continue;
solve(v,u);
if(man[u]&&man[v]){
int a=man[u],b=man[v];
if(a>b) swap(a,b);
int tempmax=max((a-1) , (len+1-b) );
if(ans > w*tempmax){
ans=w*tempmax;
ansid=id;
}
}
else{
if(ans>w*len){
ans=w*len;
ansid=id;
}
}
}
}
int main(){
int n,T,cas=1;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
initedge();
for(int i=1 ; i
#include
#include
#include
#include
#include
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
const int INF=0x3f3f3f3f;
struct Edge{
int v,next;
int id;
int w;
}E[100010*2];
int head[100010],size;
void addedge(int u,int v,int w,int id){
E[size].id=id;
E[size].v=v;
E[size].w=w;
E[size].next=head[u];
head[u]=size++;
}
void initedge(){
size = 0 ;
memset(head, -1,sizeof head);
}
int len,root;
int p[100010];
int q[100010];
int man[100010];
void dfs0(int u,int deep,int pre){
if(deep>len){
len=deep;
root=u;
}
for(int e=head[u] ; e!=-1 ; e=E[e].next){
int v=E[e].v;
if(v==pre) continue;
dfs0(v,deep+1,u);
}
}
int dep[100010];
void dfs(int u,int pre){
q[u] = pre;
dep[u] = dep[pre] + 1;
for(int e=head[u] ; e!=-1 ; e=E[e].next){
int v=E[e].v;
if(v==pre) continue;
dfs(v,u);
|