简单定向（direction）

题意：一棵树，边有权值，定向，使一个点入度权大于出度权，问：方案数。

官方题解：

树形 dp，简单来说肯定是儿子与父亲之间转移，状态与子树有关，因此让每个节点统计他的子树的答案就好。

而这道题他要求不存在路径权值呈单调递增，并且树上的边的权值是一个全排列。

不存在单调递增，那么我们肯定要做的是转化，显然就是入度的权值是满足大于出度的权值，但是这条性质我是真的没有转化出来，导致我甚至连dp的思考方向都没有多想，以后遇到树形问题一定要转化。

结论：对于任意节点，入度权大于出度权。

trick：我们把权值记录到了边偏下，那么只有根节点没有权值，那么最后统计根节点的答案就好了。

那考虑树形 dp，设 fu,0/1f_{u,0/1}，0 表示儿子指向父亲，1 表示父亲指向儿子。

显然我们考虑统计方案数，对于一个节点的不同儿子相互独立，答案运用乘法原理就好。

但现在还有个限制条件就是当前节点与他的父亲的权值同时得满足儿子的限制，那我们考虑当前节点与他的父亲的边的方向的关系，显然有两种，那么我们考虑将当前节点的所有儿子按权值从大到小排序，记录前缀积，和后缀积，前缀积记录的是单调递减的这些子树的方案数，后缀积是单调递增的这些子树的方案数，那么显然每次转移，我们通过比较与当前要统计答案的节点的与他的父亲的朝向来确定答案，到最后递归继承 1 节点自然就可以统计答案了。

关键：其实就是原先对边的穷举，转化为对 2 条边的限制关系，通过合法条件运用加法原理和乘法原理去转移就好。

求方案数，自然是一直是继承初始的方案，类似于 dp 边界，中间通过乘法原理和加法原理显然是对初始方案的扩展。

完毕。

这块是关键。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if(fa){
    //是时候和父亲的权值比较了
    long long s=suf[1];
    for(int i=1;i<=cnt;i++){
        if(val[son[i]]<val[u]) break;
        s=(s+pre[i]*suf[i+1]%mod)%mod;
    }
    f[u][0]=s;
    s=pre[cnt];
    for(int i=cnt;i>=1;i--){
        if(val[son[i]]>val[u]) break;
        s=(s+suf[i]*pre[i-1]%mod)%mod;
    }
    //父亲现在是入度权
    f[u][1]=s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+8;
vector<pair<int,int> > G[N];
long long f[N][2];
//0指向父亲，1指向儿子
long long pre[N],suf[N];
int n;
long long ans=0;
const int mod=998244353;
long long val[N];
int son[N];
void dfs(int u,int fa){
    sort(G[u].begin(),G[u].end(),greater<pair<int,int> >());
    for(auto v:G[u]){
        if(v.second==fa) continue;
        val[v.second]=v.first;
        dfs(v.second,u);
    }
    int cnt=0;
    for(auto v:G[u]){
        if(v.second==fa) continue;
        son[++cnt]=v.second;
    }
    if(cnt==0){
        f[u][0]=f[u][1]=1;
        return ;
    }
    //入度权必须是严格大于出度权
    //pre是u的儿子指向父亲的即当前u的入度权并且权值是递减的
    //从儿子中继承方案数
    pre[0]=1;
    for(int i=1;i<=cnt;i++){
        pre[i]=pre[i-1]*f[son[i]][0]%mod;
    }
    //suf则反,是大于当前父亲权值的，并且权值是递增的
    //出度权，父亲指向儿子
    suf[cnt+1]=1;
    for(int i=cnt;i>=1;i--){
        suf[i]=suf[i+1]*f[son[i]][1]%mod;
    }
    if(fa){
        //是时候和父亲的权值比较了
        long long s=suf[1];
        for(int i=1;i<=cnt;i++){
            if(val[son[i]]<val[u]) break;
            s=(s+pre[i]*suf[i+1]%mod)%mod;
        }
        f[u][0]=s;
        s=pre[cnt];
        for(int i=cnt;i>=1;i--){
            if(val[son[i]]>val[u]) break;
            s=(s+suf[i]*pre[i-1]%mod)%mod;
        }
        //父亲现在是入度权
        f[u][1]=s;
    }
    else{
        for(int i=0;i<=cnt;i++){
            ans=(ans+pre[i]*suf[i+1]%mod)%mod;
        }
    }
}
int main(){
	freopen("direction.in","r",stdin);
	freopen("direction.out","w",stdout);
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        G[u].push_back({i,v});
        G[v].push_back({i,u});
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

__END__