0表示被父亲控制，1表示被儿子控制，2表示被自己控制。f表示最少士兵数，g表示方案数。

　　转移贼难写，写了好久之后写不下去了，看了一眼题解，学习了。。。原来还可以这么搞

　　比如求f[i][1]的时候，要在所有儿子里选一个儿子的f[to][2]来转移，这有一个非常巧妙的做法，那就是从自己转移...

　　每次可以选择从f[i][1]+min(f[to][1], f[to][2])转移或者从f[i][0]+f[to][2]转移，并使得f[i][1]比f[i][0]先转移，这样的话相当于每次会从第一次取f[to][2]和已经取过f[to][2]转移，十分正确，非常好写...

　　还要注意的是如果从f[i][0]转移，方案数得加上g[i][0]*g[to][2]。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long long#define MOD(x) ((x)>=mod?(x-mod):(x))using namespace std;const int maxn=500010, inf=1e9, mod=1032992941;struct poi{
    int too, pre;}e[maxn<<1];int n, x, y, tot;int last[maxn], g[maxn][3], f[maxn][3];;void read(int &k){    int f=1; k=0; char c=getchar();    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();    k*=f;   } inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}void dfs(int x, int fa){    f[x][1]=maxn; f[x][2]=g[x][0]=g[x][1]=g[x][2]=1;    for(int i=last[x], too;i;i=e[i].pre)    if((too=e[i].too)!=fa)    {        dfs(too, x);        ll tmpf=min(maxn, min(f[x][1]+min(f[too][1], f[too][2]), f[x][0]+f[too][2])), tmpg=0;        if(f[x][1]+f[too][1]==tmpf) tmpg+=g[too][1];        if(f[x][1]+f[too][2]==tmpf) tmpg+=g[too][2], tmpg=MOD(tmpg);        f[x][1]=tmpf; g[x][1]=1ll*g[x][1]*tmpg%mod;        if(f[x][0]+f[too][2]==tmpf) g[x][1]+=1ll*g[x][0]*g[too][2]%mod, g[x][1]=MOD(g[x][1]);        f[x][0]+=f[too][1]; f[x][0]=min(maxn, f[x][0]); g[x][0]=1ll*g[x][0]*g[too][1]%mod;        tmpf=min(f[too][0], min(f[too][1], f[too][2])); tmpg=0;        if(f[too][0]==tmpf) tmpg+=g[too][0];        if(f[too][1]==tmpf) tmpg+=g[too][1], tmpg=MOD(tmpg);        if(f[too][2]==tmpf) tmpg+=g[too][2], tmpg=MOD(tmpg);        f[x][2]+=tmpf; f[x][2]=min(maxn, f[x][2]); g[x][2]=1ll*g[x][2]*tmpg%mod;    }}int main(){    read(n);    for(int i=1;i
           
            f[1][2]) printf("%d\n%d", f[1][2], g[1][2]); else printf("%d\n%d", f[1][1], MOD(g[1][1]+g[1][2]));}
           
          
         
        
       
      

　　明明答案不会爆int的。。。但是不开LL就WA，至今不明T T 神tm..f的不合法状态是inf加起来爆int了，判了一下之后终于能int过了，因为比LL快也跑到了rk10

　　为了查这个我WA了一页...