2025-11-25
人生中第一个10k+的代码！
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define lc (u<<1)
#define rc (u<<1|1)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define sed second
#define Max(a,b) ((a)<(b)?(a)=(b):1)
#define Min(a,b) ((a)>(b)?(a)=(b):1)
using namespace std;
const int N=1e5+10,inf=1e18;
namespace Fread{const int SIZE=1<<21;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}
namespace Fwrite{const int SIZE=1<<21;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
inline void putchar(char c){*S++=c;if(S==T)flush();}struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;}
#define getchar Fread ::getchar
#define putchar Fwrite ::putchar
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){char c=getchar();T f=1;while (c<'0'||c>'9'){if (c=='-')f=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while (c==' '||c=='\n')c=getchar();while(c!=' '&&c!='\n'&&c!='\r'){str[len++]=c;c=getchar();}str[len]='\0';return *this;}Reader&operator>>(string&s){char c=getchar();s.clear();while(c==' '||c=='\n')c=getchar();while(c!=' '&&c!='\n'&&c!='\r'){s+=c;c=getchar();}return*this;}Reader(){}}cin;struct Writer{template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return *this;}if(x<0){putchar('-');x=-x;}static int sta[45];int top=0;while(x){sta[++top]=x%10;x/=10;}while(top){putchar(sta[top]+'0');--top;}return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer(){}}cout;}
#define cin Fastio ::cin
#define cout Fastio ::cout
bool MS;int used,id;
int n,q,L;
int a[N];
int stmax[20][N];
pii st_upper[20][N];
pii st_lower[20][N];
int f[N],g[N];
int h[N];
int ot[N];
vector<int>edge[N];
int son[N];
vector<pii>chain[N];
vector<pii>mh[N];
vector<pii>pre[N],suf[N];
vector<int>preh[N],sufh[N];
int st[N],wson[N],deep[N],sz[N],fa[N];
int dept[N];
int dfn[N],rev[N],res;
int lg[N];
inline void merge(pii&u,pii v){
if(v.fst>u.fst)
{
u.sed=u.fst;
u.fst=v.fst;
}
else Max(u.sed,v.fst);
if(v.sed>u.fst)
{
u.sed=u.fst;
u.fst=v.sed;
}
else Max(u.sed,v.sed);
}
void init(){
res=0;
memset(f,0,sizeof f);
memset(g,0,sizeof g);
memset(h,0,sizeof h);
memset(ot,0,sizeof ot);
memset(st,0,sizeof st);
memset(wson,0,sizeof wson);
memset(deep,0,sizeof deep);
memset(sz,0,sizeof sz);
memset(fa,0,sizeof fa);
memset(son,0,sizeof son);
rep(i,1,n)
{
edge[i].clear();
chain[i].clear();
pre[i].clear();
suf[i].clear();
preh[i].clear();
sufh[i].clear();
mh[i].clear();
}
lg[1]=0;
rep(i,2,N-1)
{
lg[i]=lg[i/2]+1;
}
}
void dfs1(int u,int fa){
dept[u]=dept[fa]+a[u];
deep[u]=deep[fa]+1;
::fa[u]=fa;
sz[u]=1;
pii vl=mp(0,0);
f[u]=a[u];
for(auto v:edge[u])
if(v!=fa)
{
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[wson[u]])
wson[u]=v;
Max(f[u],f[v]+a[u]);
merge(vl,mp(f[v],0));
Max(h[u],h[v]);
mh[u].pb(mp(h[v],v));
}
Max(h[u],vl.fst+vl.sed+a[u]);
sort(mh[u].begin(),mh[u].end());
reverse(mh[u].begin(),mh[u].end());
}
void dfs2(int u,int fa,int st){
dfn[u]=++res;
rev[res]=u;
::st[u]=st;
int cnt=0;
for(auto v:edge[u])
if(v!=fa&&v!=wson[u])
{
son[v]=cnt;cnt++;
pre[u].pb(mp(f[v],0));
suf[u].pb(mp(f[v],0));
preh[u].pb(h[v]);
sufh[u].pb(h[v]);
chain[u].pb(mp(f[v],v));
}
rep(i,1,cnt-1)
{
merge(pre[u][i],pre[u][i-1]);
Max(preh[u][i],preh[u][i-1]);
}
per(i,cnt-2,0)
{
merge(suf[u][i],suf[u][i+1]);
Max(sufh[u][i],sufh[u][i+1]);
}
if(wson[u])
{
int v=wson[u];
g[v]=g[u]+a[u];
if(suf[u].size())
Max(g[v],suf[u][0].fst+a[u]);
chain[u].pb(mp(f[wson[u]],wson[u]));
dfs2(wson[u],u,st);
}
cnt=0;
for(auto v:edge[u])
if(v!=fa&&v!=wson[u])
{
g[v]=g[u]+a[u];
if(wson[u])Max(g[v],f[wson[u]]+a[u]);
if(cnt) Max(g[v],pre[u][cnt-1].fst+a[u]);
if(cnt+1<(int)suf[u].size())Max(g[v],suf[u][cnt+1].fst+a[u]);
dfs2(v,u,v);
cnt++;
}
if(fa)
chain[u].pb(mp(g[u],fa));
sort(chain[u].begin(),chain[u].end());
reverse(chain[u].begin(),chain[u].end());
}
void dfs3(int u,int fa){
int cnt=0,res=0;
if(fa)
{
for(auto [val,from]:chain[fa])
{
if(from!=u)
{
cnt++;
res+=val;
}
if(cnt==2)break;
}
Max(ot[u],res+a[fa]);
}
if(wson[u])
{
int v=wson[u];
ot[v]=ot[u];
if(suf[u].size())
Max(ot[v],sufh[u][0]);
dfs3(wson[u],u);
}
cnt=0;
for(auto v:edge[u])
if(v!=fa&&v!=wson[u])
{
ot[v]=ot[u];
if(wson[u])Max(ot[v],h[wson[u]]);
if(cnt) Max(ot[v],preh[u][cnt-1]);
if(cnt+1<(int)suf[u].size())Max(ot[v],sufh[u][cnt+1]);
dfs3(v,u);
cnt++;
}
}
int LCA,fu,fv;
int lca(int u,int v){
if(st[u]==st[v])return dfn[u]<dfn[v]?u:v;
if(deep[st[u]]>deep[st[v]])swap(u,v);
return lca(u,fa[st[v]]);
}
int getson(int u,int v){
if(u==v)return u;
while(1)
{
if(st[u]==st[v])return wson[v];
u=st[u];
if(fa[u]==v)return u;
u=fa[u];
}
}
int query(int l,int r){
if(l>r)return 0;
int g=lg[r-l+1];
return max(stmax[g][l],stmax[g][r-(1<<g)+1]);
}
pii query_upper(int l,int r){
int g=lg[r-l+1];
return max(st_upper[g][l],st_upper[g][r-(1<<g)+1]);
}
pii query_lower(int l,int r){
int g=lg[r-l+1];
return max(st_lower[g][l],st_lower[g][r-(1<<g)+1]);
}
int solve1(int u,int v,bool tag=0){
int ans=0;
if(tag)
{
if(!(dfn[u]<=dfn[v]&&dfn[v]<dfn[u]+sz[u]))Max(ans,h[u]);
if(!(dfn[v]<=dfn[u]&&dfn[u]<dfn[v]+sz[v]))Max(ans,h[v]);
Max(ans,ot[LCA]);
int cnt=0,res=0;
for(auto [val,from]:chain[LCA])
{
if(from!=fu&&from!=fv)
{
cnt++;
res+=val;
}
if(cnt==2)break;
}
for(auto [val,from]:mh[LCA])
if(from!=fu&&from!=fv)
{
Max(ans,val);
break;
}
Max(ans,res+a[LCA]);
}
if(st[u]==st[v])
{
int l=min(dfn[u],dfn[v]);
int r=max(dfn[u],dfn[v]);
l++;r--;
Max(ans,query(l,r));
return ans;
}
if(deep[st[u]]>deep[st[v]])swap(u,v);
Max(ans,query(dfn[st[v]],dfn[v]-1));
int now=fa[st[v]];
int pos=son[st[v]];
if(now!=LCA)
{
if(wson[now]) Max(ans,h[wson[now]]);
if(pos) Max(ans,preh[now][pos-1]);
if(pos+1<(int)sufh[now].size()) Max(ans,sufh[now][pos+1]);
pii val=mp(0,0);
if(pos) merge(val,pre[now][pos-1]);
if(pos+1<(int)suf[now].size()) merge(val,suf[now][pos+1]);
merge(val,mp(f[wson[now]],0));
Max(ans,val.fst+val.sed+a[now]);
}
Max(ans,solve1(u,now));
return ans;
}
int dis(int u,int v){
if(!v)return 0;
else if(dfn[v]<=dfn[u]&&dfn[u]<dfn[v]+sz[v])return dept[u]-dept[fa[v]];
else return dept[u]+dept[v]-dept[LCA]-dept[fa[LCA]];
}
namespace SGT{
struct vl
{
int premax,sufmax,maxn,sum;
vl operator+(const vl&b)const
{
vl c;
c.premax=max(premax, sum+b.premax);
c.sufmax=max(b.sufmax,b.sum+sufmax);
c.sum=sum+b.sum;
c.maxn=max({sufmax+b.premax,maxn,b.maxn});
return c;
}
}tre[N<<2];
void build(int u,int l,int r)
{
if(l==r)
{
int now=rev[l];
tre[u].maxn=tre[u].premax=tre[u].sufmax=tre[u].sum=a[now];
for(auto [w,from]:chain[now])
{
if(from==wson[now]||from==fa[now])continue;
tre[u].maxn=tre[u].premax=tre[u].sufmax=w+a[now];
break;
}
return;
}
int mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
tre[u]=tre[lc]+tre[rc];
}
vl query(int u,int l,int r,int x,int y)
{
if(x<=l&&r<=y)
{
return tre[u];
}
int mid=(l+r)/2;
if(x<=mid&&y>mid)return query(lc,l,mid,x,y)+query(rc,mid+1,r,x,y);
if(x<=mid)return query(lc,l,mid,x,y);
return query(rc,mid+1,r,x,y);
}
}using namespace SGT;
int sufmax[N];
vector<pii>opt;
void get_next(int&v,int&pos){
if(dfn[v]==opt[pos].sed)
{
pos++;
v=rev[opt[pos].fst];
}
else
{
if(opt[pos].fst<=opt[pos].sed)
v=rev[dfn[v]+1];
else
v=rev[dfn[v]-1];
}
}
void get_last(int&v,int&pos){
if(dfn[v]==opt[pos].fst)
{
pos--;
v=rev[opt[pos].sed];
}
else
{
if(opt[pos].fst<=opt[pos].sed)
v=rev[dfn[v]-1];
else
v=rev[dfn[v]+1];
}
}
int nxt(int v,int pos){
if(dfn[v]==opt[pos].sed)
{
pos++;
v=rev[opt[pos].fst];
}
else
{
if(opt[pos].fst<=opt[pos].sed)
v=rev[dfn[v]+1];
else
v=rev[dfn[v]-1];
}
return v;
}
int lst(int v,int pos){
if(dfn[v]==opt[pos].fst)
{
pos--;
v=rev[opt[pos].sed];
}
else
{
if(opt[pos].fst<=opt[pos].sed)
v=rev[dfn[v]-1];
else
v=rev[dfn[v]+1];
}
return v;
}
int hu,hv;
int val(int x,int pos){
int nt=(x==hv?0:nxt(x,pos));
int lt=(x==hu?0:lst(x,pos));
for(auto [w,from]:chain[x])
{
if((x!=hv&&from==nt)||(x!=hu&&from==lt))continue;
return w+a[x];
}
return a[x];
}
int solve2(int u,int v,int w,bool tag=0)
{
hu=u,hv=v;
opt.clear();
opt.pb(mp(0,0));
while(1)
{
if(u!=LCA)
opt.pb(mp(dfn[u],dfn[u]));
if(st[u]==st[LCA])
{
if(u!=LCA&&fa[u]!=LCA)
opt.pb(mp(dfn[u]-1,dfn[LCA]+1));
break;
}
else
{
if(u!=st[u])
opt.pb(mp(dfn[u]-1,dfn[st[u]]));
u=fa[st[u]];
}
}
opt.pb(mp(dfn[LCA],dfn[LCA]));
stack<pii>stk;
while(1)
{
if(v!=LCA)
stk.push(mp(dfn[v],dfn[v]));
if(st[v]==st[LCA])
{
if(v!=LCA&&fa[v]!=LCA)
stk.push(mp(dfn[v]-1,dfn[LCA]+1));
break;
v=LCA;
}
else
{
if(v!=st[v])
stk.push(mp(dfn[v]-1,dfn[st[v]]));
v=fa[st[v]];
}
}
while(stk.size())
{
swap(stk.top().fst,stk.top().sed);
opt.pb(stk.top());
stk.pop();
}
u=hu;v=hv;
int ans=0;
int pos=opt.size()-1;
while(v&&dis(u,lst(v,pos))-a[u]>dis(u,hv)-dis(u,v)+w)
{
if(v==hv)sufmax[v]=val(v,pos)+dis(u,hv)-dis(u,v)+w;
else sufmax[v]=max(sufmax[nxt(v,pos)],val(v,pos)+dis(u,hv)-dis(u,v)+w);
get_last(v,pos);
}
deque<pii>d;
int now=u,pn=1;
int cnt=0;
int kkk;
while(1)
{
kkk=val(now,pn)+dis(u,lst(now,pn));
while(d.size()&&val(d.back().fst,d.back().sed)+dis(u,lst(d.back().fst,d.back().sed))<=kkk)
d.pop_back();
d.push_back(mp(now,pn));
if(now==v)break;
get_next(now,pn);
cnt++;
if(cnt==L)
{
rep(i,pn,pos)
{
int nw;
if(opt[i].fst==opt[i].sed)
{
nw=rev[opt[i].fst];
}
else
{
int l=opt[i].fst;
int r=opt[i].sed;
if(i==pn)l=dfn[now];
if(i==pos)r=dfn[v];
pii vl;
if(l<r)
{
vl=query_upper(l,r);
vl.fst+=dept[u]-dept[LCA]-dept[fa[LCA]];
}
else
{
vl=query_lower(r,l);
vl.fst+=dept[u];
}
nw=vl.sed;
}
kkk=val(nw,i)+dis(u,lst(nw,i));
while(d.size()&&val(d.back().fst,d.back().sed)+dis(u,lst(d.back().fst,d.back().sed))<=kkk)
d.pop_back();
d.push_back(mp(nw,i));
}
break;
}
}
now=u,pn=1;
while(1)
{
if(d.front().fst==now)d.pop_front();
while(v!=hv&&dis(u,v)-dis(u,now)<=dis(u,lst(now,pn))+dis(u,hv)-dis(u,nxt(v,pos))+w)
{
get_next(v,pos);
kkk=val(v,pos)+dis(u,lst(v,pos));
while(d.size()&&val(d.back().fst,d.back().sed)+dis(u,lst(d.back().fst,d.back().sed))<=kkk)
d.pop_back();
d.push_back(mp(v,pos));
}
if(d.size())Max(ans,val(now,pn)+val(d.front().fst,d.front().sed)+dis(u,lst(d.front().fst,d.front().sed))-dis(u,now));
if(v!=hv)Max(ans,sufmax[nxt(v,pos)]+val(now,pn)+dis(u,lst(now,pn)));
else
{
get_next(now,pn);
vl base=vl{0,0,0,0};
rep(i,pn,pos)
{
if(opt[i].sed==opt[i].fst)
{
int kk=val(rev[opt[i].sed],i);
base=base+vl{kk,kk,kk,a[rev[opt[i].sed]]};
}
else if(opt[i].fst<opt[i].sed)
{
if(pn==i)
base=base+query(1,1,n,max(opt[i].fst,dfn[now]),opt[i].sed);
else
base=base+query(1,1,n,opt[i].fst,opt[i].sed);
}
else
{
vl g;
if(pn==i)
g=query(1,1,n,opt[i].sed,min(opt[i].fst,dfn[now]));
else
g=query(1,1,n,opt[i].sed,opt[i].fst);
swap(g.premax,g.sufmax);
base=base+g;
}
}
Max(ans,base.maxn);
break;
}
if(now==hv)break;
get_next(now,pn);
}
return ans;
}
void solve()
{
init();
cin>>n>>q>>L;
rep(i,1,n)
cin>>a[i];
rep(i,2,n)
{
int u,v;
cin>>u>>v;
edge[u].pb(v);
edge[v].pb(u);
}
dfs1(1,0);
dfs2(1,0,1);
dfs3(1,0);
rep(i,1,n)
{
int u=rev[i];
stmax[0][i]=0;
if(suf[u].size())
{
Max(stmax[0][i],sufh[u][0]);
Max(stmax[0][i],suf[u][0].fst+suf[u][0].sed+a[u]);
}
int vl=a[u];
for(auto [w,from]:chain[u])
{
if(from==wson[u]||from==fa[u])continue;
vl=w+a[u];
break;
}
st_upper[0][i]=mp(vl+dept[fa[u]],u);
st_lower[0][i]=mp(vl-dept[u],u);
}
rep(w,1,19)
rep(i,1,n-(1<<w)+1)
{
stmax [w][i]=max( stmax[w-1][i], stmax[w-1][i+(1<<(w-1))]);
st_upper[w][i]=max(st_upper[w-1][i],st_upper[w-1][i+(1<<(w-1))]);
st_lower[w][i]=max(st_lower[w-1][i],st_lower[w-1][i+(1<<(w-1))]);
}
build(1,1,n);
id++;
while(q--)
{
int u,v,w;
cin>>u>>v>>w;
LCA=lca(u,v);
fu=getson(u,LCA),fv=getson(v,LCA);
int val1=solve1(u,v,1);
int val2=solve2(u,v,w);
cout<<max(val1,val2)<<'\n';
}
}
bool MT;
signed main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
int T=1;
cin>>T;
while(T--)
solve();
cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()<<"ms\n";
}