結果
| 問題 |
No.399 動的な領主
|
| ユーザー |
 char134217728
|
| 提出日時 | 2018-01-11 16:58:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,235 bytes |
| コンパイル時間 | 2,246 ms |
| コンパイル使用メモリ | 207,560 KB |
| 最終ジャッジ日時 | 2025-01-05 07:15:31 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 19 |
コンパイルメッセージ
main.cpp:195:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
195 | main(){
| ^~~~
ソースコード
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define pcnt __builtin_popcount
#define show(x) cout<<#x<<" = "<<x<<endl;
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define fi first
#define se second
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define sz(x) (int)(x).size()
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v)
{stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;}
int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;}
void dout(double d){printf("%.12f\n",d);}
const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 200005;
struct HL{
int root;
vi head, heavy, weight, parent, sid;
vvi *G, pl;
map<int, int> hid;
void dfs(int pos, int pre){
weight[pos] = 1;
heavy[pos] = -1;
parent[pos] = pre;
head[pos] = pos;
int mw = 0, w;
each(itr, (*G)[pos]){
if(pre == *itr) continue;
dfs(*itr, pos);
w = weight[*itr];
if(w > mw) mw = w, heavy[pos] = *itr;
weight[pos] += w;
}
}
void set_head(int pos, int pre){
if(pos == head[pos]) hid[pos] = sz(hid)-1;
pl[head[pos]].pb(pos);
each(itr, (*G)[pos]){
if(pre == *itr) continue;
if(heavy[pos] == *itr){
head[*itr] = head[pos];
sid[*itr] = sid[pos] + 1;
}
set_head(*itr, pos);
}
}
struct LCA{
int ln;
vvi *G, parent;
vi depth;
void dfs(int pos, int pre, int d){
depth[pos] = d;
each(itr, (*G)[pos]){
if(pre == *itr) continue;
parent[0][*itr] = pos;
dfs(*itr, pos, d+1);
}
}
int root(int a, int b){
if(depth[a] > depth[b]) swap(a, b);
int d = depth[b] - depth[a];
FOR(i, 0, ln) if((1<<i)&d) b = parent[i][b];
if(a == b) return a;
FORR(i, ln-1, 0) if(parent[i][a] != parent[i][b]) a = parent[i][a], b = parent[i][b];
return parent[0][a];
}
void build(vvi* G, int r){
this->G = G;
int n = sz(*G);
for(ln = 0; (1<<ln) < n; ln++);
parent = vvi(n);
FOR(i, 0, ln) parent[i] = vi(n);
depth = vi(n);
dfs(r, -1, 0);
FOR(i, 1, ln)FOR(j, 0, n) parent[i][j] = (parent[i-1][j] == -1 ? -1 : parent[i-1][parent[i-1][j]]);
}
};
LCA lca;
pair<pii, pii> path(int root, int leaf){ // [root, leaf] => head_id, is_last, idx_l, idx_r
if(head[root] == head[leaf]) return mp(mp(hid[head[root]], -1), mp(sid[root], sid[leaf]));
return mp(mp(hid[head[leaf]], parent[head[leaf]]), mp(sid[head[leaf]], sid[leaf]));
}
void build(vvi* G, int r){
this->G = G;
lca.build(G, r);
int n = sz(*G);
head = vi(n);
heavy = vi(n);
weight = vi(n);
parent = vi(n);
sid = vi(n);
pl = vvi(n);
dfs(r, -1);
set_head(r, -1);
}
};
struct StarrySky{
typedef ll T1; typedef ll T2;
const T1 e_merge = 0;
const T2 e_add = 0;
T1 merge(T1 a, T1 b){
return a+b;
}
T1 addT1(T1 a, int k, int l, int r, T2 b){
return a+b*(r-l);
}
T2 addT2(T2 a, T2 b){
return a+b;
}
//###################################################
int n;
vector<T1> d;
vector<T2> s;
void init(int m){
n = 1<<(32-__builtin_clz(m-1));
d.resize(2*n-1);
s.resize(2*n-1);
fill(d.begin(), d.end(), e_merge);
fill(s.begin(), s.end(), e_add);
}
void init(vector<T1>&v){
init(v.size());
for(int j=0; j<v.size(); j++) d[j+n-1] = v[j];
for(int j=n-2; j>=0; j--) d[j] = merge(d[j*2+1], d[j*2+2]);
}
void ref(int k, int l, int r){
if(s[k] != e_add){
int mid = (l+r)/2, _k = k*2+1;
s[_k] = addT2(s[_k], s[k]);
d[_k] = addT1(d[_k], _k, l, mid, s[k]);
_k++;
s[_k] = addT2(s[_k], s[k]);
d[_k] = addT1(d[_k], _k, mid, r, s[k]);
s[k] = e_add;
}
}
T1 _section_add(int a,int b,int k,int l,int r, T2&v){
if(r<=a||b<=l){
}else if(a<=l&&r<=b){
s[k] = addT2(s[k], v);
d[k] = addT1(d[k], k, l, r, v);
}else{
ref(k, l, r);
d[k] = merge(_section_add(a, b, k*2+1, l, (l+r)/2, v), _section_add(a, b, k*2+2, (l+r)/2, r, v));
}
return d[k];
}
void section_add(int a, int b, T2 v){
_section_add(a, b, 0, 0, n, v);
}
T1 _query(int a,int b,int k,int l,int r){
if(r<=a||b<=l) return e_merge;
if(a<=l&&r<=b) return d[k];
ref(k, l, r);
return merge(_query(a, b, k*2+1, l, (l+r)/2), _query(a, b, k*2+2, (l+r)/2, r));
}
T1 query(int a,int b){
return _query(a, b, 0, 0, n);
}
};
vector<StarrySky> vss;
HL hl;
int n, q, x, y;
vvi G;
main(){
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n;
G.resize(n);
FOR(i, 0, n-1){
int a, b;
cin >> a >> b;
a--; b--;
G[a].pb(b);
G[b].pb(a);
}
return 0;
hl.build(&G, 0);
vss.resize(sz(hl.hid));
each(itr, hl.hid){
vl s = vl(sz(hl.pl[itr->fi]));
vss[itr->se].init(s);
}
cin >> q;
pair<pii, pii> t;
ll ans = 0;
FOR(i, 0, q){
cin >> x >> y;
x--; y--;
int r = hl.lca.root(x, y);
while(true){
t = hl.path(r, x);
vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, 1);
ans += vss[t.fi.fi].query(t.se.fi, t.se.se+1);
if(t.fi.se == -1) break;
x = t.fi.se;
}
while(true){
t = hl.path(r, y);
vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, 1);
ans += vss[t.fi.fi].query(t.se.fi, t.se.se+1);
if(t.fi.se == -1) break;
y = t.fi.se;
}
t = hl.path(r, r);
ans -= vss[t.fi.fi].query(t.se.fi, t.se.se+1);
vss[t.fi.fi].section_add(t.se.fi, t.se.se+1, -1);
}
cout << ans << endl;
return 0;
}