P6773 [noi2020] destiny (DP, segment tree merging)

Preface

It looks like a cancer, but it's actually a small and fresh problem ？
It's not that difficult to understand .
Violence is very strong , Praise .
Wonderful line segment tree merging skills have been added .

analysis

solution 1

How do you play with your hands ？
Most of the （ For example, I ） All inclusive .

Move the method of playing to the code, and you get a question that the author wants us to write from the data range $O(2^{m}poly)$ practice .
Think about it carefully. The tree can maintain the number of edges that are not covered ,dfs Modify it by the way , Time complexity $O(2^m{\log }^{2}n)$.
Expected score 32-40 branch .
I don't understand why it's written online $O(2^{m}m{\log }^{2}n)$ ah

solution 2

You don't really write solutions 1 Is that right .
The form of this question is very dp.
Design $f_{x,d}$ Representation node $x$ The subtree of is processed , The maximum depth of the ancestor of the unresolved atavism chain is $d$ Number of alternatives .
It is easy to transfer in the form of a backpack on a tree , Time complexity $O(n\min (n,m))$, Expected score $64$ branch .
But the crap I wrote can't make a complete binary tree , The result is only $56$ Divide up （ sad ）.
（ Prefixes and optimizations are easier to write , And then we can introduce the following positive solution ）

solution 3

Observe dp Transfer , It is found that the transfer is very regular , It seems that you can maintain a segment tree and so on .
Then garbage, I can't think of segment tree merging , You can only think of maintaining a segment tree for each heavy chain after the heavy chain is divided , The subscript only stores the depth limit in the subtree （ Similar to discretization ）, So the sum of the leaves of all segment trees is $O(n\log n)$, After the heavy chain is handled, the violence merges with the chain head father , Probably $O(n{\log }^{2}n)$ Of .
Expected score 88 branch .
It is very simple to realize , So just Hu Hu , It didn't write .
If it's fake, spray it gently （ flee

---

Gorgeous dividing line .
Then my level is stuck in this place .
The next step is to solve the problem .

solution 4

hold dp The transfer is written in prefix and form ：
$$d{p}_{x,i}=d{p}_{x,i}^{\prime }\sum _{j=0}^{de{p}_x}d{p}_{s,j}+d{p}_{x,i}^{\prime }\sum _{j=0}^{i}d{p}_{s,j}+d{p}_{s,i}\sum _{j=0}^{i-1}d{p}_{x,j}$$
That is to say ：
$$d{p}_{x,i}=d{p}_{x,i}^{\prime }(su{m}_{s,de{p}_x}+su{m}_{s,i})+d{p}_{s,i}su{m}_{x,i-1}$$
Notice that in addition to $su{m}_{s,de{p}_x}$ Is a constant , Everything else is closely related to subscripts .

Consider line segment tree merging .
Make $s1=su{m}_{s,de{p}_x}+su{m}_{s,i},s2=su{m}_{x,i-1}$.
Recurse the left subtree before merging , In recursive right subtree , Constantly updated $s1,s2$ that will do .
I think it's easier for you to understand the code than to listen to me .

ll s1,s2;
int merge(int x,int y,int l,int r){
    
  if(!x&&!y) return 0;
  else if(!x||!y){
    
    if(x){
    
      add(s2,tr[x].sum);
      Mul(x,s1);
      return x;
    }
    else{
    
      add(s1,tr[y].sum);
      Mul(y,s2);
      return y;
    }
  }
  else if(l==r){
    
    int now=New();
    int a=tr[x].sum,b=tr[y].sum;
    add(s1,b);
    tr[now].sum=(s1*a+s2*b)%mod;;
    add(s2,a);
    return now;
  }
  pushdown(x);pushdown(y);
  int now=New();  
  tr[now].ls=merge(tr[x].ls,tr[y].ls,l,mid);
  tr[now].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
  pushup(now);
  return now;
}

Then the problem is finished .
Complexity of time and space $O(n\log n)$, Expected score 100 branch .

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("ok\n")
inline ll read(){
    
  ll x(0),f(1);char c=getchar();
  while(!isdigit(c)) {
    if(c=='-')f=-1;c=getchar();}
  while(isdigit(c)) {
    x=(x<<1)+(x<<3)+c-'0';c=getchar();}
  return x*f;
}

const int N=5e5+100;
const int inf=1e9+100;
const int mod=998244353;
const bool Flag=0;
#define add(x,y) (((x)+=(y))>=mod&&((x)-=mod))

int n,m;

#define mid ((l+r)>>1)
struct node{
    
  int ls,rs;
  ll sum,mul=1;
}tr[N*40];
int tot;
vector<int>e[N];
inline int New(){
    
  tr[++tot].mul=1;
  return tot;
}
inline void Mul(int x,int w){
    
  if(x){
    
      tr[x].sum=tr[x].sum*w%mod;
      tr[x].mul=tr[x].mul*w%mod;
  }
  return;
}
inline void pushdown(int x){
    
  if(tr[x].mul!=1){
    
    Mul(tr[x].ls,tr[x].mul);
    Mul(tr[x].rs,tr[x].mul);
    tr[x].mul=1;
  }
  return;  
}
inline void pushup(int k){
    
  tr[k].sum=(tr[tr[k].ls].sum+tr[tr[k].rs].sum)%mod;
}
ll ask(int k,int l,int r,int x,int y){
    
  if(!k) return 0;
  if(x<=l&&r<=y) return tr[k].sum;
  pushdown(k);
  ll res(0);
  if(x<=mid) add(res,ask(tr[k].ls,l,mid,x,y));
  if(y>mid) add(res,ask(tr[k].rs,mid+1,r,x,y));
  return res;
}
ll s1,s2;
int merge(int x,int y,int l,int r){
    
  //if(l>lim) return 0;
  if(!x&&!y) return 0;
  else if(!x||!y){
    
    if(x){
    
      add(s2,tr[x].sum);
      Mul(x,s1);
      return x;
    }
    else{
    
      add(s1,tr[y].sum);
      Mul(y,s2);
      //printf("(%d %d) s2=%lld sum=%lld\n",l,r,s2,tr[y].sum);
      return y;
    }
  }
  else if(l==r){
    
    int now=New();
    int a=tr[x].sum,b=tr[y].sum;
    add(s1,b);
    tr[now].sum=(s1*a+s2*b)%mod;;
    add(s2,a);
    return now;
  }
  pushdown(x);pushdown(y);
  int now=New();  
  tr[now].ls=merge(tr[x].ls,tr[y].ls,l,mid);
  tr[now].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);
  pushup(now);
  return now;
}
void ins(int &k,int l,int r,int p){
    
  if(!k) k=New();
  if(l==r){
    
    tr[k].sum++;
    return;
  }
  pushdown(k);
  if(p<=mid) ins(tr[k].ls,l,mid,p);
  else ins(tr[k].rs,mid+1,r,p);
  pushup(k);
}
void print(int k,int l,int r){
    
  if(!k) return;
  if(l==r){
    
    printf("d=%d dp=%lld\n",l,tr[k].sum);
    return;
  }
  pushdown(k);
  print(tr[k].ls,l,mid);
  print(tr[k].rs,mid+1,r);
  return;
}
int rt[N];

int dep[N],d[N];
void init(int x,int fa){
    
  dep[x]=dep[fa]+1;
  for(int to:e[x]){
    
    if(to==fa) continue;
    init(to,x);
  }
  return;
}
void dfs(int x,int fa){
    
  for(int to:e[x]){
    
    if(to==fa) continue;
    dfs(to,x);
  }
  ins(rt[x],0,n,d[x]);
  for(int to:e[x]){
    
    if(to==fa) continue;
    s1=ask(rt[to],0,n,0,dep[x]);
    s2=0;
    rt[x]=merge(rt[x],rt[to],0,n);
    //printf("----------%d->%d\n",x,to);
    //print(rt[x],0,n);
    //puts("");
  }
  return;
}

signed main(){
    
#ifndef ONLINE_JUDGE
  freopen("a.in","r",stdin);
  freopen("a.out","w",stdout);
#endif
  n=read();
  for(int i=1;i<n;i++){
    
    int x=read(),y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  init(1,0);
  m=read();
  for(int i=1;i<=m;i++){
    
    int u=read(),v=read();
    d[v]=max(d[v],dep[u]);
  }
  dfs(1,0);
  printf("%lld\n",ask(rt[1],0,n,0,0));
  return 0;
}