欢乐游戏鸡

分析

线性表

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define MX 300003
#define wi first
#define di second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int N, M, W[MX];
vector<pii> qur[MX];

template <typename T> void read(T& x)
{
x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = x*10+c-'0', c = getchar();
}

struct GRAPH
{
int fst[MX], nxt[MX], v[MX], lnum;
int fa[MX][20], mx[MX][20];
int dep[MX], len[MX], son[MX];

{
nxt[++lnum] = fst[nu];
fst[nu] = lnum;
v[lnum] = nv;
}

void dfs(int x, int f, int d)
{
dep[x] = d;
fa[x][0] = f;
mx[x][0] = W[f];
for(int i=fst[x]; i; i=nxt[i])
{
dfs(v[i], x, d+1);
len[x] = max(len[x], len[v[i]]);
if(!son[x] || len[v[i]]>len[son[x]]) son[x] = v[i];
}
len[x]++;
}

void init()
{
dfs(1, 0, 1);
for(int j=1; j<20; j++)
for(int i=1; i<=N; i++)
mx[i][j] = max(mx[i][j-1], mx[fa[i][j-1]][j-1]),
fa[i][j] = fa[fa[i][j-1]][j-1];
}

int jump(int x, int d)
{
int ret = 0;
for(int i=19; i>=0; i--)
if(dep[fa[x][i]] >= d)
ret = max(ret, mx[x][i]),
x = fa[x][i];
return ret;
}
} G;

void input()
{
int a, b;
for(int i=1; i<N; i++)
{
}
for(int i=1; i<=M; i++)
{
scanf("%d%d", &a, &b);
qur[a].push_back(make_pair(b, i));
}
}

pii f[MX];
ll s[MX],ans[MX];
int lft[MX], rgt[MX];
int dfn[MX], dfc;

void insert(int tar, const pii& nod)    //nod.di can't be greater than f[lft[tar]].di
{
while(lft[tar]<=rgt[tar] && f[lft[tar]].wi<=nod.wi) lft[tar]++;
if(lft[tar]>rgt[tar] || f[lft[tar]].di!=nod.di)
{
f[--lft[tar]] = nod;
int p = lft[tar];
s[p] = s[p+1] + 1ll*(f[p+1].wi-f[p].wi)*f[p+1].di;
}
}

void merge(int tar, int src)
{
static pii tmp[MX];
int t = 0;
while(lft[tar]<=rgt[tar] && f[lft[tar]].di < f[rgt[src]].di) tmp[++t] = f[lft[tar]++];
while(t && lft[src]<=rgt[src])
{
if(tmp[t].di > f[rgt[src]].di) insert(tar, tmp[t--]);
else insert(tar, f[rgt[src]--]);
}
while(t) insert(tar, tmp[t--]);
while(lft[src]<=rgt[src]) insert(tar, f[rgt[src]--]);
}

ll query(int x, int w, int d)
{
int p = lower_bound(f+lft[x], f+rgt[x]+1, make_pair(w, 0)) - f;
if(p == lft[x])
{
ll retr = 1ll * w * f[p].di;
return retr - 1ll * w * d;
}
else
{
ll retl = s[lft[x]] - s[p-1] + 1ll * f[lft[x]].wi * f[lft[x]].di;
ll retr = 1ll * (w-f[p-1].wi) * f[p].di;
return (retl + retr) - 1ll * w * d;
}
}

void dfs(int x)
{
dfn[x] = ++dfc;
if(G.son[x])
{
dfs(G.son[x]);
lft[x] = lft[G.son[x]];
rgt[x] = rgt[G.son[x]];
}
else lft[x] = dfn[x]+1, rgt[x] = dfn[x];
for(int i=G.fst[x]; i; i=G.nxt[i])
if(G.v[i] != G.son[x])
dfs(G.v[i]), merge(x, G.v[i]);
for(auto it=qur[x].begin(); it!=qur[x].end(); it++)
ans[it->second] = query(x, G.jump(it->first, G.dep[x]+1), G.dep[x]) + G.dep[it->first] - G.dep[x];
insert(x, make_pair(W[x], G.dep[x]));
}

int main()
{
input();
G.init();
dfs(1);
for(int i=1; i<=M; i++) printf("%lld\n", ans[i]);
return 0;
}