题意分析
题目链接
这里借鉴了\(Youngsc\)以及\(hzwer\)的思路
首先由于涉及到了区间异或最值的问题
所以我们需要使用到\(01Trie\)树
这里贴一道板子题
然后对一个位置\(x\)
我们维护四个位置\(l_1,l_2,r_1,r_2\)
\(l_1\) 从\(x\)往左数第一个大于\(x\)的位置
\(l_2\) 从\(x\)往左数第二个大于\(x\)的位置
\(r_1\) 从\(x\)往右数第一个大于\(x\)的位置
\(r_2\) 从\(x\)往右数第二个大于\(x\)的位置
那么\(x\)作为次大值的区间就是\([l_1+1,r_2-1]\)以及\([l_2+1,r_1-1]\)
至于维护这四个位置 我们使用\(set\)就可以了
把位置按照权值从大到小排序
然后依次插入 就可以了
CODE:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 1008
#define IL inline
#define M 1008611
#define D double
#define mod 1000000007
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
T __=0,___=1;char ____=getchar();
while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
_=___ ? __:-__;
}
char getch() {
char ch = getchar();
while(ch != '<' && ch != '>') ch = getchar();
return ch;
}
/*-------------OI使我快乐-------------*/
int T,n,tot;
int to[N<<1],nex[N<<1],head[N<<1],w[N<<1];
int siz[N];
ll C[N][N],dp[N][N],tmp[N];
IL void add(int x,int y,int z)
{to[++tot]=y;nex[tot]=head[x];head[x]=tot;w[tot]=z;}
IL void dp_cdy(int now,int v)
{
for(R int i=1;i<=n;++i) tmp[i]=dp[now][i],dp[now][i]=0;
for(R int i=1;i<=siz[now];++i)
for(R int j=i;j<=i+siz[v]-1;++j)
dp[now][j]=(dp[now][j]+C[j-1][i-1]*C[siz[now]+siz[v]-j][siz[now]-i]%mod*tmp[i]%mod*(dp[v][siz[v]]-dp[v][j-i]+mod)%mod)%mod;
}
IL void dp_wzy(int now,int v)
{
for(R int i=1;i<=n;++i) tmp[i]=dp[now][i],dp[now][i]=0;
for(R int i=1;i<=siz[now];++i)
for(R int j=i+1;j<=siz[v]+i;++j)
dp[now][j]=(dp[now][j]+C[j-1][i-1]*C[siz[now]+siz[v]-j][siz[now]-i]%mod*tmp[i]%mod*dp[v][j-i]%mod)%mod;
}
IL void dfs(int now,int fat)
{
siz[now]=1;dp[now][1]=1;
for(R int i=head[now];i;i=nex[i])
{
int v=to[i];
if(v==fat) continue;
dfs(v,now);
if(w[i]) dp_cdy(now,v);
else dp_wzy(now,v);
siz[now]+=siz[v];
}
for(R int i=1;i<=siz[now];++i) dp[now][i]=(dp[now][i]+dp[now][i-1])%mod;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(T);
for(R int i=0;i<=1000;++i) C[i][0]=1;
for(R int i=1;i<=1000;++i)
for(R int j=1;j<=i;++j)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
// for(R int i=1;i<=6;++i)
// for(R int j=1;j<=i;++j)
// printf("%lld%c",C[i][j],(j==i ? '\n':' '));
while(T--)
{
read(n);tot=0;
memset(dp,0,sizeof dp);
memset(head,0,sizeof head);
for(R int i=1,x,y;i<n;++i)
{
char z;
read(x);z=getch();read(y);++x;++y;
add(x,y,z=='<');add(y,x,z=='>');
// printf("%d %c %d\n",x,z,y);
}
dfs(1,0);
// for(R int i=1;i<=n;++i) printf("%d%c",siz[i],(i==n ? '\n':' '));
printf("%lld\n",dp[1][n]);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}