///~~~LOTA~~~///
#include "city.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define append push_back
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define mod 1000000000
#define MAXN 100001
ll ans[MAXN];
ll cnt[MAXN];
ll tcnt[MAXN];
ll dist[MAXN];
int vis[MAXN];
ll tdist[MAXN];
vector<int> a[MAXN];
vector<int> par[MAXN];
int lca(int x){
int v,u,p,q,r,s;
v=par[x][0];
u=par[x][1];
p=par[v][0];
q=par[v].back();
r=par[u][0];
s=par[u].back();
if(p==r || p==s)
return p;
if(q==r || q==s)
return q;
return 0;
}
void compute(int v){
ll o,p,q;
cnt[v]+=1;
vector<int> vec;
for(auto& i:a[v]){
if(i!=par[v][0] &&
i!=par[v].back())
vec.append(i);
}
for(auto& i:vec){
cnt[v]+=cnt[i];
dist[v]=(dist[v]+dist[i]+cnt[i])%mod;
}
ans[v]+=dist[v];
for(int i=0;i<vec.size();i++){
for(int j=i+1;j<vec.size();j++){
p=(cnt[vec[j]]*(dist[vec[i]]+cnt[vec[i]]))%mod;
q=(cnt[vec[i]]*(dist[vec[j]]+cnt[vec[j]]))%mod;
ans[v]=(ans[v]+p+q)%mod;
}
}
if(par[v].size()>1){
o=lca(v);
p=par[v][0];
q=par[v][1];
tcnt[p]+=cnt[v];
tcnt[q]+=cnt[v];
tdist[p]+=dist[v]+cnt[v];
tdist[q]+=dist[v]+cnt[v];
cnt[o]+=cnt[v];
dist[o]=(dist[o]+dist[v]+2*cnt[v])%mod;
}
cnt[v]-=tcnt[v];
dist[v]-=tdist[v];
}
void bfs(){
vis[1]=1;
par[1].append(0);
vector<int> u,v{1};
vector<vector<int>> vec;
while(!v.empty()){
vec.append(v);
for(auto& j:v){
for(auto& i:a[j]){
if(i!=par[j][0] &&
i!=par[j].back())
par[i].append(j);
if(!vis[i])
u.append(i);
vis[i]=1;
}
}
swap(v,u);
u.clear();
}
reverse(all(vec));
for(auto& i:vec)
for(auto& j:i)
compute(j);
}
int DistanceSum(int n,int x[MAXN],int y[MAXN]){
map<pii,int> z;
int m,o,p,q,r;
for(int i=0;i<n;i++){
z[{x[i],y[i]}]=i+1;
if(z[{x[i],y[i]-1}]){
a[z[{x[i],y[i]-1}]].append(i+1);
a[i+1].append(z[{x[i],y[i]-1}]);
}
if(z[{x[i],y[i]+1}]){
a[z[{x[i],y[i]+1}]].append(i+1);
a[i+1].append(z[{x[i],y[i]+1}]);
}
if(z[{x[i]-1,y[i]}]){
a[z[{x[i]-1,y[i]}]].append(i+1);
a[i+1].append(z[{x[i]-1,y[i]}]);
}
if(z[{x[i]+1,y[i]}]){
a[z[{x[i]+1,y[i]}]].append(i+1);
a[i+1].append(z[{x[i]+1,y[i]}]);
}
}
bfs();
o=0;
for(int i=1;i<=n;i++)
o=(o+ans[i])%mod;
return o;
}
Compilation message
city.cpp:2:10: fatal error: city.h: No such file or directory
2 | #include "city.h"
| ^~~~~~~~
compilation terminated.
