Styles in TikZ trees not working as expected

The main problem is that your styles for the edges should be applied to the child commands not the node ones. This is what I show in the second solution. Probably better is styling the levels. I'll give this first.

Styling the levels

\documentclass{article}

\usepackage{tikz}

\begin{document}

\begin{tikzpicture}[
  every node/.style={minimum size=4mm, inner sep=0.5mm},
  level 1/.style={every child/.style={edge from parent/.style={draw,dashed}}},
  level 2/.style={every child/.style={edge from parent/.style={draw,solid}}},
  level 4/.style={every child/.style={edge from
  parent/.style={draw,dashed}},sibling distance=5mm},
  normal/.style={circle,draw,solid},
  acc/.style={circle,thick,solid,draw=green!50,fill=green!2},
  rej/.style={circle,thick,solid,draw=red!50,fill=red!20},
  semithick]

  \node (root) {}
    child[level distance=11mm] { node[normal] {x}
      child {node[acc] {x1}
        child { node[normal] {} child child}
        child { node[normal] {} child child}
      }
      child {node[rej] {x2} }
      child {node[normal] {x3}
        child {node[normal] {} child }
        child {node[acc] {} child child }
        child {node[normal] {} child child child}
      }
  }; 
\end{tikzpicture}

\end{document}

This assumes cut off at uniform depth. The style for level 2 is inherited by lower levels, so you specify styles for the first, second and last levels. If the cut off is not at uniform depth, you can instead write children on the last level as

child { edge from parent[dashed] }

producing a descending dashed line.

Style on child

\documentclass{article}

\usepackage{tikz}

\begin{document}

\begin{tikzpicture}[
  every node/.style={minimum size=4mm, inner sep=0.5mm},
  normal/.style={circle,draw},
  invis/.style={draw=none},
  border/.style={ edge from parent/.style={dashed,draw} },
  normaledge/.style={ edge from parent/.style={solid,draw}},
  acc/.style={circle,thick,draw=green!50,fill=green!2},
  rej/.style={circle,thick,draw=red!50,fill=red!20},
  semithick]

  \node[invis] (root) {}
    child[level distance=11mm,border] { node[normal] {x}
      child[normaledge] {node[acc] {x1}
        child[border] {node {} }
        child[border] {node {} }
        child[border] {node {} }
      }
      child[normaledge] {node[rej] {x2} }
      child[normaledge] {node[normal] {x3}
        child[border] {node[invis] {} }
        child[border] {node[invis] {} }
        child[border] {node[invis] {} }
      }
  }; 
\end{tikzpicture}

\end{document}

I have introduced a normaledge style for edges that are not borders.

Just a quick demonstration with Forest. The major advantages of Forest lie in its power, flexibility and concise syntax. Regularities in content and styling can be turned into automated configuration rules and trees themselves can be specified very concisely. Since Forest is based on TikZ, the power of the host package is also available.

For example,

\begin{forest}
  bordered tree,
  [
    [x, border
      [x1, acc, for descendants=border
        [][][]
      ]
      [x2, rej]
      [x3, for children=border
        [][][]
      ]
    ]
  ]
\end{forest}

specifies the target tree:

while the following partly explains the first and partly shows one or two additional tricks,

\begin{forest}
  bordered tree,
  [
    [x, border, normal
    [x1, acc, for descendants=border, label=left:\texttt{for descendants}
        [][.,label=left:bordered children [][]][]
      ]
      [x2, rej]
      [x3, normal, for children=border, label=right:\texttt{for children}
        [][.,label=right:unbordered children [][]][, for current and ancestors={edge+=blue}]
      ]
    ]
  ]
\end{forest}

which produces:

Complete code:

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\forestset{
  declare boolean={border}{0},
  bordered tree/.style={
    for tree={
      minimum size=4mm, 
      inner sep=0.5mm,
      edge+={semithick},
      semithick,
    },
    before typesetting nodes={
      where border={
        edge+={dashed, draw},
      }{},
      where={isodd(n_children)}{
        tempcounta/.process={
          Ow+n {n children}{(##1+1)/2}
        },
        for n={
          >  R {tempcounta} % doesn't work to plug the above in directly ??'
        }{calign with current edge},
      }{},
      where content={}{}{normal},
    },
  },
  /tikz/.cd,
  normal/.style={circle,draw},
  invis/.style={draw=none},
  acc/.style={circle,thick,draw=green!50,fill=green!2},
  rej/.style={circle,thick,draw=red!50,fill=red!20},
}
\begin{document}
\begin{forest}
  bordered tree,
  [
    [x, border
      [x1, acc, for descendants=border
        [][][]
      ]
      [x2, rej]
      [x3, for children=border
        [][][]
      ]
    ]
  ]
\end{forest}
\begin{forest}
  bordered tree,
  [
    [x, border, normal
    [x1, acc, for descendants=border, label=left:\texttt{for descendants}
        [][.,label=left:bordered children [][]][]
      ]
      [x2, rej]
      [x3, normal, for children=border, label=right:\texttt{for children}
        [][.,label=right:unbordered children [][]][, for current and ancestors={edge+=blue}]
      ]
    ]
  ]
\end{forest}
\end{document}