// Esti <3 //\ šťastia pre nás :)// you're already the best// _// ^ ^ //// >(O_O)<___//// \ __ __ \// \\ \\ \\\\ #include <bits/stdc++.h>using namespace std; //#pragma GCC optimize("O3","unroll-loops")//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("O3")#pragma GCC target("popcnt") using ll = long long;#define int long long#define forn(i,n) for(int i=0; i<(n); ++i)#define pb push_back#define pi pair<int,int>#define f first#define s second #define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend() mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());const int inf = 1e18;const int mod = 1e9+7;//998244353; // \\:smiling_face_with_3_hearts: :smiling_face_with_3_hearts: :smiling_face_with_3_hearts: //vidime sa veľmi skoro, moje slnko const int N = 30005; int t[21][21][N]; void add(int i, int j, int k, int x) { for(;k<N;k|=k+1) t[i][j][k]+=x;}int sum(int i, int j, int r) { int q=0; for(;r>=0;r=(r&(r+1))-1) q+=t[i][j][r]; return q;} int par[N], top[N], sz[N], d[N];int ind[N], inv[N];int nxt=0;vector<int> adj[N]; void dfs(int u, int p) { par[u]=p; sz[u]=1; for(auto&v:adj[u]) { if (v==p) continue; d[v]=d[u]+1; dfs(v,u); sz[u]+=sz[v]; }}void dfs(int u, int p, int t) { ind[u]=nxt++; inv[ind[u]]=u; top[u]=t; int mx=-1; for(auto&v:adj[u]) { if (v==p) continue; if (mx==-1) mx=v; if (sz[v] > sz[mx]) v=mx; } if (mx==-1) return; dfs(mx,u,t); for(auto&v:adj[u]) { if (v==p || v==mx) continue; dfs(v,u,v); }} int go[N][15];int jump(int u, int x) { forn(j,15) if ((x>>j)&1) u=go[u][j]; return u;} int lca(int u, int v) { if (d[u]<d[v]) swap(u,v); u=jump(u,d[u]-d[v]); if (u==v) return u; for(int j=14; j>=0; --j) { if (go[u][j] == go[v][j]) continue; u=go[u][j], v=go[v][j]; } return par[u];} int f[20];int s[20];int fs=0, ss=0;void qadd(int u, int v, int z) { int l = lca(u,v); fs=0, ss=0; while (u!=l) { f[fs++]=u; u=par[u]; } f[fs++]=u; while (v!=l) { s[ss++]=v; v=par[v]; } for (int i=ss-1; i>=0; --i) f[fs++]=s[i]; int k=fs; assert(k<=20); forn(i,20) { int u = f[i%k]; t[0][i][u]+=z; }} ll qry(int u, int t) { ll ans=0; while (u!=0) { forn(i,t+1) ans+=::t[0][i][u]; u=par[u]; } forn(i,t+1) ans+=::t[0][i][u]; return ans;}ll query(int u, int v, int t) { if (t<0) return 0; ll ans = 0; int l = lca(u,v); ans += qry(u,t); ans += qry(v,t); ans -= 2ll*qry(l,t); forn(i,t+1) { ans+=::t[0][i][l]; } return ans;} void solve() { int n; cin>>n; forn(i,n-1) { int u,v; cin>>u>>v; --u, --v; adj[u].pb(v); adj[v].pb(u); } dfs(0,0); dfs(0,0,0); forn(i,n) go[i][0]=par[i]; for(int j=1; j<15; ++j) forn(i,n) go[i][j]=go[go[i][j-1]][j-1]; int k; cin>>k; forn(i,k) { int u,v; cin>>u>>v; --u, --v; qadd(u,v,1); } int q; cin>>q; forn(i,q) { int t; cin>>t; if (t==1) { int u,v; cin>>u>>v; --u, --v; qadd(u,v,1); } else if (t==2) { int u,v; cin>>u>>v; --u, --v; qadd(u,v,-1); } else { int u,v,a,b; cin>>u>>v>>a>>b; --u, --v; ll ans = query(u,v,b); ans -= query(u,v,a-1); cout<<ans<<'\n'; } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; //cin>>t; while (t--) solve(); return 0;}
Compilation message
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/10/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x24): undefined reference to `main'
collect2: error: ld returned 1 exit status
