problem
solution
这是一道一个顶六个的好题!!!
说一下各档部分分怎么写吧。
先看一下(S_i=1)和(T_i=1)的部分分怎么写。
如果(S_i=1)
当且仅当第(i)个点的深度(dep_i=w_i)时，该点可以观察到人。且观察到的人数为终点位于其子树内的人数。
如果(T_i=1)
这时第(i)个点能观察到的人数就是子树内起点深度=(dep_i+w[i])的人数。用个桶记录下来这个值。
如果得到该子树内(dep[s_i]=dep_i+w[i])的数量呢？
其实很简单。当第一次(bfs)到点(i)时，记录下桶中(dep_i+w[i])的值，(dfs)整颗子树之后再得到一个值。将两个值作差即可。
下面说满分做法
将路径分为从(s)到(lca)和从(lca)到(t)两部分讨论。
先看从(s)到(lca)这部分。
那么对于一个点(i)就是要找(dep[lca]<=dep[i])且(dep_s=dep_i+w_i)的数量。
不考虑红色部分限制的话，就和(S_i=1)的部分分同样做法。
然后看(lca)到(t)这部分
对于一个点(i)就是要找(dep[lca]<=dep[i])且(len - (dep[t]-dep[i])=w[i])即(w[i] - dep[i] = len - dep[t])的数量((len)表示该路径长度)。
这个不考虑红色部分限制的话，也可以用一个桶维护出来。
然后考虑解决红色部分限制
其实只要在dfs完一个点的子树后，将以该点为(lca)的路径贡献全部从桶中删除即可。
code
#include<cstdio>
#include<iostream>
#include<ctime>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n,m;
namespace BF1 {
const int N = 1010;
int a[N],b[N];
void main() {
for(int i = 1;i < n;++i) {read();read();}
for(int i = 1;i <= n;++i) {
int k = read();
if(!k) b[i] = 1;
}
int ans = 0;
for(int i = 1;i <= m;++i) {
int x = read(),y = read();
a[x]++;
}
for(int i = 1;i <= n;++i)
printf("%d ",a[i] * b[i]);
}
}
namespace BF2 {
int a[1010];
void main() {
for(int i = 1;i < n;++i) {read();read();}
for(int i = 1;i <= n;++i) read();
for(int i = 1;i <= m;++i) {
int x = read(),y = read();
a[x]++;
}
for(int i = 1;i <= n;++i)
printf("%d ",a[i]);
}
}
namespace BF3 {
const int N = 1010;
struct node {
int v,nxt;
}e[N << 1];
int w[N],ans[N];
int head[N],ejs;
void add(int u,int v) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int dfs(int u,int fa,int V,int now) {
if(u == V) {
ans[u] += w[u] == now;
return 1;
}
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
if(dfs(v,u,V,now + 1)) {
ans[u] += (w[u] == now);
return 1;
}
}
return 0;
}
void main() {
for(int i = 1;i < n;++i) {
int u = read(),v = read();
add(v,u);add(u,v);
}
for(int i = 1;i <= n;++i) w[i] = read();
for(int i = 1;i <= m;++i) {
int u = read(),v = read();
dfs(u,0,v,0);
}
for(int i = 1;i <= n;++i) printf("%d ",ans[i]);
}
}
namespace BF4 {
const int N = 100010;
vector<int>v[N];
int w[N],ans[N];
int erfen(int pos,int x) {
int l = 0,r = v[pos].size() - 1,ret = r + 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(v[pos][mid] >= x) ret = mid,r = mid - 1;
else l = mid + 1;
}
return ret + 1;
}
void main() {
for(int i = 1;i < n;++i) read(),read();
for(int i = 1;i <= n;++i) w[i] = read();
for(int i = 1;i <= m;++i) {
int u = read(),V = read();
v[u].push_back(V);
}
for(int i = 1;i <= n;++i) sort(v[i].begin(),v[i].end());
for(int i = 1;i <= n;++i) {
int k = i - w[i];
if(w[i] == 0) {
ans[i] += v[k].size();continue;
}
if(k > 0) {
// int p = erfen(k,i);
// ans[i] += v[k].size() - p + 1;
for(vector<int>::iterator it = v[k].begin();it != v[k].end();++it) {
if(*it >= i) ans[i]++;
}
}
k = i + w[i];
if(k <= n) {
// int p = erfen(k,i);
// ans[i] += p - 1;
for(vector<int>::iterator it = v[k].begin();it != v[k].end();++it)
if(*it <= i) ans[i]++;
}
}
for(int i = 1;i <= n;++i) printf("%d ",ans[i]);
}
}
namespace BF5 {
const int N = 100010;
struct node {
int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int siz[N],dep[N];
void dfs(int u,int fa) {
dep[u] = dep[fa] + 1;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
dfs(v,u);
siz[u] += siz[v];
}
}
int w[N];
void main() {
for(int i = 1;i < n;++i) {
int u = read(),v = read();
add(u,v);add(v,u);
}
for(int i = 1;i <= n;++i) w[i] = read();
for(int i = 1;i <= m;++i) {
int x = read(),y = read();
siz[y]++;
}
dep[0] = -1;
dfs(1,0);
for(int i = 1;i <= n;++i) {
if(dep[i] == w[i]) printf("%d ",siz[i]);
else printf("0 ");
}
}
}
namespace BF6 {
const int N = 100010;
struct node {
int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int w[N],dep[N],ans[N];
int tong[N << 1],siz[N << 1];
void solve(int u,int fa) {
dep[u] = dep[fa] + 1;
int k = tong[dep[u] + w[u]];
tong[dep[u]] += siz[u];
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
solve(v,u);
}
ans[u] = tong[dep[u] + w[u]] - k;
}
void main() {
for(int i = 1;i < n;++i) {
int u = read(),v = read();
add(v,u);add(u,v);
}
for(int i = 1;i <= n;++i) w[i] = read();
for(int i = 1;i <= m;++i) {
int x = read(),y = read();
siz[x]++;
}
solve(1,0);
for(int i = 1;i <= n;++i) printf("%d ",ans[i]);
}
}
namespace BF7 {
const int N = 300000,logN = 20;
struct node {
int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}
int dep[N],w[N],lca[N][20];
void get_lca(int u,int fa) {
dep[u] = dep[fa] + 1;
for(int i = 1;i < logN;++i) lca[u][i] = lca[lca[u][i - 1]][i - 1];
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v == fa) continue;
lca[v][0] = u;
get_lca(v,u);
}
}
int LCA(int x,int y) {
if(dep[x] < dep[y]) swap(x,y);
for(int i = logN - 1;i >= 0;--i)
if(dep[lca[x][i]] >= dep[y]) x = lca[x][i];
for(int i = logN - 1;i >= 0;--i)
if(lca[x][i] != lca[y][i]) x = lca[x][i],y = lca[y][i];
if(x == y) return x;
return lca[x][0];
}
vector<int>vs[N],vt[N],st[N];
int ans[N],siz[N];
int stong[N << 1],ttong[N << 1];
void dfs(int u,int fa) {
int ks = stong[dep[u] + w[u]],kt = ttong[w[u] - dep[u] + N];
stong[dep[u]] += siz[u];
for(vector<int>::iterator it = st[u].begin();it != st[u].end();++it) ttong[*it]++;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
if(v != fa) dfs(v,u);
}
for(vector<int>::iterator it = vt[u].begin();it != vt[u].end();++it) ttong[*it]--;
ans[u] = stong[dep[u] + w[u]] - ks + ttong[w[u] - dep[u] + N] - kt;
for(vector<int>::iterator it = vs[u].begin();it != vs[u].end();++it) stong[*it]--;
}
void main() {
for(int i = 1;i < n;++i) {
int u = read(),v = read();
add(u,v);add(v,u);
}
for(int i = 1;i <= n;++i) w[i] = read();
get_lca(1,0);
for(int i = 1;i <= m;++i) {
int s = read(),t = read();
int k = LCA(s,t),len = dep[s] + dep[t] - dep[k] * 2;
vs[k].push_back(dep[s]);
vt[k].push_back(len - dep[t] + N);
st[t].push_back(len - dep[t] + N);
siz[s]++;
}
dfs(1,0);
for(int i = 1;i <= n;++i) printf("%d ",ans[i]);
}
}
int main() {
n = read(),m = read();
if(n == 991) {BF1::main();return 0;}
if(n == 992) {BF2::main();return 0;}
if(n == 993) {BF3::main();return 0;}
if(n == 99994) {BF4::main();return 0;}
if(n == 99995) {BF5::main();return 0;}
if(n == 99996) {BF6::main();return 0;}
BF7::main();
return 0;
}
/*
5 3
1 2
2 3
3 4
4 5
1 1 2 2 3
2 4
1 3
1 5
7 4
1 2
1 3
2 4
2 5
3 6
3 7
1 1 1 2 3 2 4
1 2
1 5
1 6
1 7
7 4
1 2
1 3
2 4
2 5
3 6
3 7
2 1 1 1 1 0 1
4 1
5 1
6 1
7 1
*/