在SPOJ上交TLE求助

#include<bits/stdc++.h>
#define int long long
#define double long double
#define INF INT_MAX
using namespace std;
const int maxn=3e5+5;
int n,q,cnt;
int a[maxn];
int f[maxn],deap[maxn],siz[maxn],son[maxn];
int id[maxn],p[maxn],top[maxn];
vector<pair<int,int> > g[maxn];
int s1[maxn],s2[maxn];
void dfs1(int dq,int fa,int sum) {
	f[dq]=fa,deap[dq]=sum,siz[dq]=1;
	int maxson=-1;
	for(int i=0; i<g[dq].size(); i++) {
		if(g[dq][i].first==fa) continue;
		a[g[dq][i].first]=g[dq][i].second;
		dfs1(g[dq][i].first,dq,sum+1);
		siz[dq]+=siz[g[dq][i].first];
		if(maxson==-1 || siz[g[dq][i].first]>siz[maxson]) maxson=g[dq][i].first,son[dq]=g[dq][i].first;
	}
	return;
}
void dfs2(int dq,int fa) {
	id[dq]=++cnt,p[cnt]=a[dq],top[dq]=fa;
	if(!son[dq]) return;
	dfs2(son[dq],fa);
	for(int i=0; i<g[dq].size(); i++) {
		if(g[dq][i].first==f[dq] || g[dq][i].first==son[dq]) continue;
		dfs2(g[dq][i].first,g[dq][i].first);
	}
	return;
}
struct Tree {
	int val,mx;
#define sum(dq) t[dq].val
#define mx(dq) t[dq].mx
} t[maxn<<4];
void up_date(int dq) {
	sum(dq)=sum(dq*2)+sum(dq*2+1);
	mx(dq)=max(mx(dq*2),mx(dq*2+1));
}
void build(int dq,int l,int r) {
	if(l==r) {
		sum(dq)=mx(dq)=p[l];
		return;
	}
	int mid=(l+r)/2;
	build(dq*2,l,mid);
	build(dq*2+1,mid+1,r);
	up_date(dq);
}
void change_sum(int dq,int ll,int rr,int l,int r,int d) {
	if(l<=ll && rr<=r) {
		sum(dq)=mx(dq)=d;
		return;
	}
	int mid=(ll+rr)/2;
	if(l<=mid) change_sum(dq*2,ll,mid,l,r,d);
	if(r>mid) change_sum(dq*2+1,mid+1,rr,l,r,d);
	up_date(dq);
}
int ask_mx(int dq,int ll,int rr,int l,int r) {
	if(l<=ll && rr<=r) return mx(dq);
	int mid=(ll+rr)/2;
	int k=-INF;
	if(l<=mid) k=max(k,ask_mx(dq*2,ll,mid,l,r));
	if(r>mid) k=max(k,ask_mx(dq*2+1,mid+1,rr,l,r));
	return k;
}
int askk_mx(int x,int y) {
	int res=-INF;
	while(top[x]!=top[y]) {
		if(deap[top[x]]<deap[top[y]]) {
			res=max(res,ask_mx(1,1,n,id[top[y]],id[y]));
			y=f[top[y]];
		} else {
			res=max(res,ask_mx(1,1,n,id[top[x]],id[x]));
			x=f[top[x]];
		}
	}
	if(deap[x]<deap[y]) res=max(res,ask_mx(1,1,n,id[x]+1,id[y]));
	else res=max(res,ask_mx(1,1,n,id[y]+1,id[x]));
	return res;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T;
	cin>>T;
	while(T--) {
		cnt=0;
		cin>>n;
		for(int i=1;i<=n;i++) g[i].clear();
		for(int i=1; i<n; i++) {
			int u,v,w;
			cin>>u>>v>>w;
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
			s1[i]=u,s2[i]=v;
		}
		dfs1(1,0,1);
		dfs2(1,1);
		build(1,1,n);
		while(true) {
			int x,y;
			string op;
			cin>>op;
			if(op=="DONE") break;
			cin>>x>>y;
			if(op=="CHANGE") {
				if(deap[s1[x]]>deap[s2[x]]) change_sum(1,1,n,id[s1[x]],id[s1[x]],y);
				else change_sum(1,1,n,id[s2[x]],id[s2[x]],y);
			}
			if(op=="QUERY") {
				if(x==y) cout<<0<<endl;
				else cout<<askk_mx(x,y)<<endl;
			}
		}
	}
	return 0;
}