C++常用模板

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e3+10,mod=998244353;
ll n,a[N],jc[N],dp[N],ans;
void init(){
	jc[0]=1;
	for(int i=1;i<N;i++) jc[i]=jc[i-1]*i%mod;
} 
ll ksm(ll a,ll b){
	ll ct=1;
	while(b){
		if(b&1) ct=ct*a%mod;
		b>>=1,a=a*a%mod;
	}
	return ct;
}
ll C(ll n,ll m){
	return jc[n]*ksm(jc[n-m],mod-2)%mod*ksm(jc[m],mod-2)%mod;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;init();
	for(int i=1;i<=n;i++) cin>>a[i];
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+10;
ll b,p,q,k,n,m,t[N*4],a[N],lazy[N*4];
void build(ll rt,ll l,ll r){
	if(l==r){t[rt]=a[l];return;}
	ll mid=l+r>>1;
	build(rt<<1,l,mid);
	build((rt<<1)+1,mid+1,r);
	t[rt]=t[rt<<1]+t[(rt<<1)+1];
}
void fun(ll rt,ll l,ll r,ll v){
	t[rt]+=(r-l+1)*v;
	lazy[rt]+=v;
}
void pushdown(ll rt,ll l,ll r){
	ll mid=l+r>>1;
	fun(rt<<1,l,mid,lazy[rt]);
	fun((rt<<1)+1,mid+1,r,lazy[rt]);
	lazy[rt]=0;
}
void update(ll rt,ll l,ll r,ll rl,ll rr,ll k){
	if(r<rl||rr<l) return;
	if(l>=rl&&rr>=r){fun(rt,l,r,k);return;}
	pushdown(rt,l,r);
	ll mid=l+r>>1;
	update(rt<<1,l,mid,rl,rr,k);
	update((rt<<1)+1,mid+1,r,rl,rr,k);
	t[rt]=t[rt<<1]+t[(rt<<1)+1];
}
ll query(ll rt,ll l,ll r,ll rl,ll rr){
	if(r<rl||rr<l) return 0;
	if(l>=rl&&rr>=r) return t[rt];
	pushdown(rt,l,r);
	ll mid=l+r>>1;
	return query(rt<<1,l,mid,rl,rr)+query((rt<<1)+1,mid+1,r,rl,rr);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
  
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+10,M=2e5+10,inf=(1ll<<31)-1;
ll n,m,s,dist[N],x,y,v;
vector<pair<ll,ll> > e[M];
set<pair<ll,ll> > q;
void dijkstra(ll s){
	q.clear();
	for(int i=1;i<=n;i++) dist[i]=inf;
	dist[s]=0;
	for(int i=1;i<=n;i++) q.insert({dist[i],i});
	while(!q.empty()){
		ll x=q.begin()->second;
		q.erase(q.begin());
		if(dist[x]==inf) break;
		for(auto y:e[x]){
			if(dist[x]+y.second<dist[y.first]){
				q.erase({dist[y.first],y.first});
				dist[y.first]=dist[x]+y.second;
				q.insert({dist[y.first],y.first});
			}
		}
	}
	for(int i=1;i<=n;i++)
		cout<<dist[i]<<" ";
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
    	cin>>x>>y>>v;
    	e[x].push_back({y,v});
	}
	dijkstra(s);
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+10;
ll n,a,b,s,m,l,ans,tot,f[N][55],h[N],de[N],r;
struct P{
	ll a,n;
}d[N*2];
void dfs(ll now,ll fa){
	f[now][0]=fa,de[now]=de[fa]+1;
	for(int i=1;i<=20;i++)
		f[now][i]=f[f[now][i-1]][i-1];
	for(int i=h[now];i!=0;i=d[i].n)
		if(d[i].a!=fa)
			dfs(d[i].a,now);
}
ll lca(ll x,ll y){
	if(de[x]>de[y]) x^=y^=x^=y;
	for(int i=20;i>=0;i--)
		if(de[f[y][i]]>=de[x])
			y=f[y][i];
	if(x==y) return x;
	for(int i=20;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		d[++tot].a=b,d[tot].n=h[a],h[a]=tot;
		d[++tot].a=a,d[tot].n=h[b],h[b]=tot;
	}
	dfs(s,0);
	while(m--){		
		cin>>l>>r;
		cout<<lca(l,r)<<"\n";
	}
	return 0;
}